Mac的投票
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 52(12 users) Total Accepted: 12(10 users) Rating: Special Judge: No
Description
Mac 占领了Dust星球，为了占领整个星系，他必须先离开Du星。但是，离开之前他需要选出Dust星的新首领替他接管星球。
Dust星上有 N 个城市，Mac 需要制作 M 个容量相等投票箱用于每个城市的投票。Mac 已经知道了每个城市的人口数量，并且每个人都会参加自己城市的投票行动。
Mac 现在想知道他制作投票箱的容量最少是多少，这样在他分配给每个城市一定数量的邮箱后，每个城市的邮箱都可以装下该城市所有人的投票。
Input
多组测试数据，对于每组测试数据：
输入的第一行为两个整数 N(1<=N<=500,000),B(N<=B<=2,000,000),分别表示城市总数和邮箱的总数。
接下来的N 行，每行一个整数 ai(1<=ai<=5,000,000) 表示该城市的人口总数。
当 N 和 M 都为-1 时，输入结束。
Output
对于每组测试数据，输出一个整数，表示投票箱的最小容量，每组输出占一行。
Sample Input
2 7
200000
500000
4 6
120
2680
3400
200
-1 -1
Sample Output
100000
1700
题解
二分枚举答案就好了
int a[maxn],c[maxn];
int main()
{
int n,b;
while(~scanf("%d%d",&n,&b))
{
if(n==-1&&b==-1)
break;
int r=0,l=0,mid;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
r=max(a[i],r);
}
int num,ans=inf;
while(l<r)
{
num=b;
mid=(l+r)/2;
for(int i=1;i<=n;i++)
{
c[i]=a[i];
while(c[i]>mid)
{
num--;
c[i]-=mid;
}
if(mid>=c[i])
{
num--;
}
}
if(num>=0)
{
r=mid;
ans=min(ans,mid);
}
else if(num<0) l=mid+1;
}
printf("%d
",ans);
}
return 0;
}