题意
有 \(n\) 个城市，\(b\) 个投票箱，第 \(i\) 个城市有 \(a_i\) 人，每个人均有一张票，将 \(b\) 个投票箱分给 \(n\) 个城市，每个城市的票分摊在投票箱里，求所有城市中最多的投票箱中票的最小值（多组数据）。
解法
最大值最小，考虑二分答案。若二分出的结果大于 \(b\)，说明当前答案小于最终答案，应继续增加；小于或等于 \(b\) 同理。注意左边界应为 \(1\)，右边界应为 \(\max\limits_{i=1}^{n} a_i\)。
代码
int a[5000001];
bool check(int mid,int n,int b)
{
int ans=0,i;
for(i=1;i<=n;i++)
{
ans+=ceil(1.0*a[i]/mid);
}
return ans>b;
}
int main()
{
int n,b,i,l,r,mid,ans;
while(cin>>n>>b)
{
if(n==-1&&b==-1)
{
break;
}
else
{
l=1;
r=ans=0;
for(i=1;i<=n;i++)
{
cin>>a[i];
r=max(r,a[i]);//处理右边界
}
while(l<=r)//二分
{
mid=(l+r)/2;
if(check(mid,n,b)==true)
{
ans=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
cout<<ans<<endl;
}
}
return 0;
}
类似题目
luogu P1577 切绳子，luogu P2440 木材加工，luogu P1873 [COCI2011-2012#5] EKO / 砍树均与本题类似，也可当做二分答案练习题来做。