Codeforces Round #499 (Div. 2) ---- B Planning The Expedition
程序员文章站
2022-06-04 08:24:02
...
神奇的一题,没考虑复杂度就去dfs了,然后t了,才发现没有那么复杂。
其实不用考虑分的方法,粮食的总量是固定的,假设存在一个答案k,每一种粮食分成k份,第i份粮食完最少的一份就是 a[i] / k
如果所有粮食最少的份加起来比总人数大,说明这些粮食存在一种分法可以让n个人坚持k天,同时因为天数越多,消耗的粮食的量越大,所以可以二分搜索答案,因为数据不大,其实暴力也可以,如果是二分搜索记得对答案特别判断是否可行。
代码如下
#include <bits/stdc++.h>
using namespace std;
int n,m,v;
map<int, int> mp;
int check(int mid){
int ans = 0;
for (auto now : mp){
ans += now.second / mid;
}
if (ans < n) return 0;
else return 1;
}
int main(){
cin >> n >> m;
for (int i=1;i<=m;i++){
cin >> v;
mp[v]++;
}
int l = 0,r = 100;
while (l != r) {
int mid = (l + r) >> 1;
if (mid == 0){
cout << 0 << endl; return 0;
}
if (check(mid)) l = mid + 1;
else r = mid;
}
while (check(l)) l++;
cout << l - 1 << endl;
return 0;
}
推荐阅读
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Codeforces Round #461 (Div. 2) B. Magic Forest(异或的性质)
-
Codeforces Round #663 (Div. 2) B. Fix You
-
Codeforces Round #658 (Div. 2) B. Sequential Nim
-
B. Power Sequence(数学+枚举)Codeforces Round #666 (Div. 2)
-
Codeforces Round #666 (Div. 2)B. Power Sequence(等比数列)
-
Codeforces Round #664 (Div. 2) B. Boboniu Plays Chess
-
Codeforces Round #632 (Div. 2)(A+B)
-
Educational Codeforces Round 93 (Rated for Div. 2) B - Substring Removal Game
-
Codeforces Round #278 (Div. 2)B?? Candy Boxes_html/css_WEB-ITnose