题解：SP10108 BALLOT - Distributing Ballot Boxes

zhangyizexiaozhi · 2026-10-22 20:36:47 · 题解

题目传送门。

博客食用。

题目大意

有 n 个城市，共 b 个投票箱，每个城市至少分配 1 个箱子。

每个城市的人必须在该城市的箱子投票。

求一种分配方案，使得所有箱子中投票人数的最大值最小。

思路分析

1. 最大值最小化，标准的二分答案。
2. 若所有城市所需箱子之和 \leq b，则 m 可行，可以尝试更小的值；否则 m 太小，需要增大。
3. 左边界 l=1。
4. 右边界 r=\max(a_i)。
5. 向上取整用 ceil(a[i]/m。

代码实现

#include<cstdio>
int n,b,a[500001];
bool check(int m){// 判断每箱最多 m 人时，所需箱子总数是否不超过 b
    int s=0;
    for(int i=0;i<n;++i){
        s+=ceil(a[i]/m);
    }
    return s<=b;
}
int main(){
    int l,r,m;
    while(cin>>n>>b,n!=-1){
        r=0;
        for(int i=0;i<n;++i){
            cin>>a[i];
            if(a[i]>r){
                r=a[i];
            }
        }
        for(l=1;l<r;){
            m=(l+r)/2;
            if(check(m)){
                r=m;
            }
            else l=m+1;
        }
        cout<<l;
    }
}