【二分枚举】杭电 hdu 4190 Distributing Ballot Boxes
?
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------// Copyright (c) 2012 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=4190 Name : 4190 Distributing Ballot Boxes Date : Monday, April 02, 2012 Time Stage : 1 hour Result:56917012012-04-02 19:37:39Accepted4190375MS2204K1434 BC++pyyTest Data :Review :受华神指导，终于AC了……//----------------------------------------*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include <vector>#include <algorithm>#include <iostream>#include <queue>using namespace std ;#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value#define max(x, y) ((x) > (y) ? (x) : (y))#define min(x, y) ((x) < (y) ? (x) : (y))#define INF (0x3f3f3f3f)#define MAXN (500002)#define DB /##/#define LL __int64intn, b;intMax, Min, Mid;intcity[MAXN];int solve(){int i, t = b;for (i = 0; i < n; ++i){int r = city[i] / Mid;if (city[i] % Mid){++r;}t -= r;}return t;}int main(){int i;while (scanf("%d %d", &n, &b), n != -1 && b != -1){Max = 0;Min = 1;for (i = 0; i < n; ++i){scanf("%d", &city[i]);Max = max(Max, city[i]);}Max++;while (Min < Max){Mid = (Min + Max) / 2;if (solve() < 0)Min = Mid + 1;else // 箱子可以不用完～一开始以为必须分完，结果屡次WAMax = Mid;}printf ("%d\n", Max);}return 0;}?