欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #499 (Div. 2) ---- B Planning The Expedition

程序员文章站 2022-06-04 08:24:02
...

Codeforces Round #499 (Div. 2) ---- B Planning The Expedition

 

神奇的一题,没考虑复杂度就去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;
}