题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4190
题目大意:
有N个城市,M个投票箱。
然后是N行,表示每个城市的人口数。
现在每个城市所有的人要投票,投票箱的大小可以无限大(投票箱全部相同,大小相等),我们现在要求的是最小的投票箱容纳量。
解题思路:
如果N == M,则容量肯定为城市人口数最多的那个。
如果N < M,我们当然要把M全部用光,因为用的箱子越多,平均值越小。这样,我们就可以二分枚举人口数作为投票箱的容量,如果对于当前容量,我们枚举所有城市需要的箱子数目,小于需要的箱子就说明还可以再小,如果需要的箱子数大于给出的箱子数,说明最小容量就在当前容量+1到刚才/2的容量数。
比如
2 7
20
50
2个城市,7个箱子,0号城市20人,1号城市50人。
我们令l=1,r=50
现在枚举中间值(如果可以继续,我们将r/2,不可以的话l=mid+1)mid=(r + l) / 2,25时候需要的箱子为1+2=3<7,所以执行r /= 2,l = 1, r = 25, 之后的次序为l = 1, r = 25, l = 1, r = 13,这时候发现mid=7不满足题意,所以说明要找的容量在mid+1到r中间,所以令l=mid+1,然后l = 8, r = 13, l = 8, r = 10, l = 10, r = 10,这时候容量由一个区间缩为一个点,说明找到了答案。所以这个就是最小的容量。
代码如下:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<climits> using namespace std; int a[500010]; int main() { int city, box, res, r, l, mid; int sum; bool flag; while(scanf("%d%d", &city, &box)) { if(city == - 1 && box == -1) break; res = 0; for(int i = 0; i < city; ++i) { scanf("%d", &a[i]); res = max(res, a[i]); } if(city == box) { printf("%d\n", res); continue; } l = 1, r = res; while(l < r) { flag = true; sum = 0; mid = (l + r) >> 1; for(int i = 0; i < city; ++i) { sum += ceil(a[i] * 1.0 / mid); //测试中间值 if(sum > box) flag = false; } if(flag) r = mid; //中间值可以就减半 else l = mid + 1; //不可以则mid+1 } printf("%d\n", r); } return 0; }