Description
今天,科丁王国举行总统大选,18岁或以上的每一位居民都被要求投票,政府有许多投票箱,不幸的是,负责城市间运送投票箱的工人几个月前被解雇了。
因此,政府无法将投票箱灵活运送到每个城市、让选民投票;你的任务是计算一个有效的投票箱分配过程,使得:
1)每个城市至少分配一个投票箱,政府会平均安排选民到自己城市的投票箱中投票
2)投票箱能接纳的最大选民数量最小化
Input
每个测试用例的第一行包含整数N(1<=N<=500000)表示城市数量、B(N<=B<=2000000)表示投票箱数量。
以下N行中的每一行包含一个整数Ai(1<=Ai<=5000000),表示第i个城市的人口。
每种每个用例结束后都有一个空白行。输入的最后一行将包含-1 -1,不应进行处理。
用例解析如下:
1)第一个测试用例中,两个投票箱分别指向第一个城市和第二个城市,并且在有效的分配下、投票箱中的最大选民数至少有10万人。
2)第二个测试用例中,分别将1、2、2、1个投票箱分配给4个城市,那么:
-第一个城市的1个投票箱有120人投票
-第二个城市的2个投票箱有1340人投票
-第三个城市的2个投票箱有1700人投票
-第四个城市的1个投票箱有200人投票
这种情况下,投票箱中的最大选民数至少有1700人
Output
对于每个用例,程序输出一个整数,即在最有效分配的情况下,投票箱中的最大选民数至少有多少?
2 7
200000
500000
4 6
120
2680
3400
200
-1 -1