首页 > 代码库 > ACM投票——二分法

ACM投票——二分法

2024-08-07 16:53:50   212人阅读

问题描述
有N个城市，每个城市有Ai个人。
现在要开始投票，每个人有一张票。
作为领导者，你有B个箱子，你必须要将这B个箱子分发到N个城市去，每个城市至少需要一个箱子。
每个人都必须要投票，不能弃票，也就是说要把票丢进箱子里去(每个城市有Ai张票)。
现在问你，怎么分配这B个箱子才能使这些所有箱子里中票数最大的那个箱子里的票最少?

输入
输入包含一个数N(1<=N<=500,000)和B(N<=B<=2,000,000)。
接下来N行包含N个数，每个数Ai(1<=Ai<=5,000,000)表示每个城市的人数。
输入N为-1，B为-1时结束。

输出
输出那个带兵量最多的将领所带的士兵数。

样例输入
2 7
200000
500000
4 6
120
2680
3400
200
-1 -1

样例输出
100000
1700


分析

若每个城市都先分得一个箱子，那么目前的答案就是max(Ai(1<=i<=n))。所以，我们必须要给最大值的那个城市还需要至少分配一个箱子，那么答案肯定不再是那个城市(也有可能有某个城市的人数跟该城市人数一样，那么答案还是没变)。
接下来如果你还有箱子，你肯定要给次大值的那个城市至少再分配一个箱子；
接下来如果你还有箱子，你肯定要给次次大值的那个城市至少再分配一个箱子；
接下来如果你还有箱子，你肯定要给次次次大值的那个城市至少再分配一个箱子；
接下来如果你还有箱子，你肯定要给次次次次大值的那个城市至少再分配一个箱子；
。。。
直到什么时候呢？
直到原先那个最大值城市的票数的一半(奇数需要再加1)大于等于了你刚刚从大到小排列的城市的那个票数，为什么？
因为那个城市的后面的票数肯定小于等于那个城市，那么这些城市中没有一个票数是比那个最大值城市的票数的一半还要大，也就是说当前状态下，所有城市中，原先那个最大值城市的票数的一半成了当前最大值。

解题：你想到了什么？——二分！
我们二分票数，票数范围是1到某个城市的最大票数。
记l=1, r=max,那么mid=(1+max)/2;
假设mid就是答案，那么我们需要统计一下一共需要几个箱子。

int num = 0;

for (int i = 1; i <= n; i++)

{

    if (a[i] % mid) num += a[i] / mid + 1;

    else num += a[i] / mid;

}



那么最后需要num个箱子，但是我们有B个箱子，所以需要比较一下。
如果num>B，说明我们需要的箱子不够，也就是说票数不小于mid值的那些城市中有些城市分不到足够的箱子，所以，我们的最终答案肯定是大于num的。那么二分范围落在[mid + 1, max]。
如果num<=B，说明我们需要的箱子很够，也就是说票数不小于mid值的那些城市中所有城市都能分到足够的箱子，所以，我们的最终答案肯定是小于等于num的。那么二分范围落在[1, mid]。
然后继续二分，直到最终的范围l>=r为止结束。

ACM投票——二分法


联系
我们