首页 > ACM题库 > HDU-杭电 > HDU 4190-Distributing Ballot Boxes-分治-[解题报告]HOJ
2015
05-23

HDU 4190-Distributing Ballot Boxes-分治-[解题报告]HOJ

Distributing Ballot Boxes

问题描述 :

Today, besides SWERC’11, another important event is taking place in Spain which rivals it in importance: General Elections. Every single resident of the country aged 18 or over is asked to vote in order to choose representatives for the Congress of Deputies and the Senate. You do not need to worry that all judges will suddenly run away from their supervising duties, as voting is not compulsory.
The administration has a number of ballot boxes, those used in past elections. Unfortunately, the person in charge of the distribution of boxes among cities was dismissed a few months ago due to nancial restraints. As a consequence, the assignment of boxes to cities and the lists of people that must vote in each of them is arguably not the best. Your task is to show how efficiently this task could have been done.
The only rule in the assignment of ballot boxes to cities is that every city must be assigned at least one box. Each person must vote in the box to which he/she has been previously assigned. Your goal is to obtain a distribution which minimizes the maximum number of people assigned to vote in one box.
In the first case of the sample input, two boxes go to the fi rst city and the rest to the second, and exactly 100,000 people are assigned to vote in each of the (huge!) boxes in the most efficient distribution. In the second case, 1,2,2 and 1 ballot boxes are assigned to the cities and 1,700 people from the third city will be called to vote in each of the two boxes of their village, making these boxes the most crowded of all in the optimal assignment.

输入:

The fi rst line of each test case contains the integers N (1<=N<=500,000), the number of cities, and B(N<=B<=2,000,000), the number of ballot boxes. Each of the following N lines contains an integer ai,(1<=ai<=5,000,000), indicating the population of the ith city.
A single blank line will be included after each case. The last line of the input will contain -1 -1 and should not be processed.

输出:

The fi rst line of each test case contains the integers N (1<=N<=500,000), the number of cities, and B(N<=B<=2,000,000), the number of ballot boxes. Each of the following N lines contains an integer ai,(1<=ai<=5,000,000), indicating the population of the ith city.
A single blank line will be included after each case. The last line of the input will contain -1 -1 and should not be processed.

样例输入:

2 7
200000
500000

4 6
120
2680
3400
200

-1 -1

样例输出:

100000
1700

题目链接: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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/niushuai666/article/details/7421980