A17090. 侗族鼓楼游客分配
填空题
中等
知识点
题目描述
侗族鼓楼游客分配
题目描述
侗族鼓楼是民族文化地标，景区为保护古建，限制每日游客总量为m人。现有n个旅行团报名，每个团人数已知，需筛选出人数之和不超过m的最多旅行团，优先选择人数少的团队，让更多游客体验鼓楼文化。请计算最多可接待的旅行团数量及对应总人数。
输入格式
第一行输入两个整数n（2≤n≤15）和m（10≤m≤100）；第二行输入n个整数，分别表示每个旅行团人数。
输出格式
输出两个整数，分别为最多可接待的旅行团数量和对应总人数。
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for(int i=0; i<n; i++) cin >> a[i];
sort(a.begin(), a.end());
int cnt = 0, sum = 0;
for(int x : a){
if(sum + x <= m){
sum += x;
cnt++;
} else break;
}
cout << cnt << " " << sum << endl;
return 0;
}答案解析
1. 读取输入的n和m，分别表示旅行团数量和游客总量上限。
2. 读取n个旅行团的人数并存储到数组或列表中。
3. 将旅行团按人数从小到大排序，优先选择人数少的团队以容纳更多团体。
4. 初始化计数器记录已选团队数量和累加器记录当前总人数。
5. 遍历排序后的团队列表，逐个将团队人数累加到总人数中，同时增加团队计数。
6. 当前累加总人数超过m时，终止遍历。
7. 输出最终的团队数量和对应的总人数。
8. 确保在累加过程中不超出m的前提下，使团队数量最大化。 知识点 使用贪心算法解决较为简单的问题、简单的贪心算法、STL中string, vector, set, map的使用方法、编写循环结构的程序、循环结构、数组的遍历、桶排序、冒泡排序、选择排序、插入排序、快速排序、归并排序等多种排序方法、基本的输入输出方法、使用贪心算法解决较为简单的问题、桶排序、冒泡排序、选择排序、插入排序、快速排序、归并排序等多种排序方法、STL中string, vector, set, map的使用方法、编写循环结构的程序、基本的输入输出方法、变量的定义、数组的遍历
上一题
下一题