题解：SP10108 BALLOT - Distributing Ballot Boxes

· · 题解

题意

有 n 座城市，有 b 个投票箱，每座城市有 a_i 张票。现在要求将 b 个投票箱分到所有城市里面，每个城市里面的人会将票均匀的投到他所在城市的投票箱里面。要求票最多的投票箱里面票最少是多少。

思路

看到要求最多的最少，直接往二分答案上面想。发现此题的答案确实具有单调性，如果 w 可以满足，那么所有小于等于 w 都可以满足。

简单讲讲 check 函数，假设一个城市有 a_i 张票，我们要让它票数最多的投票箱里面的票数小于等于 mid，那么他需要 \lceil \frac{a_i}{mid}\rceil 个投票箱。于是我们每次 check 时求出需要的总投票箱即可。

最后注意此题有多组数据。

代码

#include<bits/stdc++.h>
using namespace std;
int n,b,a[500005],l,r,ans;
inline bool check(int qwq){
    int sum=0; 
    for(int i=1;i<=n;i++){
        sum+=ceil(1.0*a[i]/qwq);//加上该城市需要的投票箱数
        if(sum>b){//超出了，退出
            return 0;
        }
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    while(cin>>n>>b){
        if(n==-1&&b==-1){
            return 0;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        l=0,ans=0,r=2000000;
        while(l<=r){
            int mid=(l+r>>1);
            if(check(mid)){
                r=mid-1;
                ans=mid;
            }
            else{
                l=mid+1;
                ans=mid+1;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

AC 记录。