【二分枚举】杭电 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;}