给定 m个食物，其中第 i个食物的种类为 ai。
请你设计一个食物套餐，对于该套餐：
- 唯一要求是设计好的套餐必须恰好包含 n个食物。
- 具体包含多少种食物，以及包含哪些种类的食物，不做要求，任你安排。
- 每种食物具体包含多少个，不做要求，任你安排。
我们的目标是通过合理安排套餐中包含的食物内容，从而使得利用给定食物，可以制作出的该套餐的数量越多越好。
输出能够制作出的套餐的最大可能数量。
输入格式
第一行包含两个整数 n,m。
第二行包含 m个整数 a1,a2,…,am。
输出格式
一个整数，表示能够制作出的套餐的最大可能数量。
如果根本不可能制作出任何套餐，则输出 0。
数据范围
前 4 个测试点满足 1≤m≤10。
所有测试点满足 1≤n≤100，1≤m≤100，1≤ai≤100。
输入样例1：
4 10 1 5 2 1 1 1 2 5 7 2
输出样例1：
2
输入样例2：
100 1 1
输出样例2：
0
输入样例3：
2 5 5 4 3 2 1
输出样例3：
1
输入样例4：
3 9 42 42 42 42 42 42 42 42 42
输出样例4：
3
解法：枚举答案or二分答案
枚举：
#include <bits/stdc++.h> using namespace std; int n, m; int a[105]; // 此题数据量不大 vector<pair<int, int>> b; // 种类，数量 int main() { // 输出能够制作出的套餐的最大可能数量 cin >> n >> m; int u; for (int i = 0; i < m; i++) { cin >> u; a[u]++; // 种类，数量 } if (n > m) { cout << 0; return 0; } if (n == m) { cout << 1; return 0; } for (int i = 0; i < 105; i++) { // 缩小范围 if (a[i] != 0) // 种类i的数量a[i]!=0 { b.push_back(make_pair(i, a[i])); } } // 枚举答案 int ans = m / n; // 最多有m/n个套餐 for (int i = ans; i >= 0; i--) { // 看每种食物是否可以提供给每份套餐几个，加起来看是否满足n int num = 0; // 最后与n比较 num:为每个套餐提供num个 for (vector<pair<int, int>>::iterator it = b.begin(); it != b.end(); it++) { num += (*it).second / i; } if (i == 0) { cout << 0; return 0; } else if (num >= n) { cout << i; return 0; } } }
二分：
#include <bits/stdc++.h> using namespace std; int n, m; int a[105]; // 此题数据量不大 vector<pair<int, int>> b; // 种类，数量 bool check(int t) // t为套餐个数 这里是对是否找到答案的判断 { int sum = 0; for (vector<pair<int, int>>::iterator it = b.begin(); it != b.end(); it++) { sum += (*it).second / t; } if (sum >= n) return true; else return false; } int main() { // 输出能够制作出的套餐的最大可能数量 cin >> n >> m; int u; for (int i = 0; i < m; i++) { cin >> u; a[u]++; // 种类，数量 } if (n > m) { cout << 0; return 0; } if (n == m) { cout << 1; return 0; } for (int i = 0; i < 105; i++) { // 缩小范围 if (a[i] != 0) // 种类i的数量a[i]!=0 { b.push_back(make_pair(i, a[i])); } } // 二分答案 int ans = m / n; // 最多有m/n个套餐 0~ans二分 int l = 0, r = ans; while (l < r) { int mid = (l + r + 1) / 2; if (check(mid)) { l = mid; } else r = mid - 1; } cout << l; }
二分模板：
while (l < r) { int mid = l + r >> 1; //(l+r)/2 if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; }
尽量往左找目标
while (l < r) { int mid = l + r + 1 >> 1; //(l+r+1)/2 if (check(mid)) l = mid; else r = mid - 1; }
尽量往右找目标
