HDU - 4190 Distributing Ballot Boxes

题意：有n个城市和m个信箱（信箱可以无限大），再给出n个城市的人口，每个城市最起码要有一个信箱，该城市的人只能把信投到自己城市的信箱里，求最小的信箱大小

思路：二分，我们将信箱的大小作为我们二分的值

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 500010;

int arr[MAXN];
int city,box;

int main(){
    while (scanf("%d%d",&city,&box) != EOF){
        if (city == -1 && box == -1)
            break;
        int res = 0;
        for (int i = 0; i < city; i++){
            scanf("%d",&arr[i]);
            res = max(res,arr[i]);
        }
        if (city == box){
            printf("%d\n",res);
            continue;
        }
        int l = 1,r = res;
        int flag, sum;
        while (l < r){
            int mid = (l+r)>>1;
            flag = 1;
            sum = 0;
            for (int i = 0; i < city; i++){
                sum += ceil(arr[i]*1.0/mid);
                if (sum > box)
                    flag = 0;
            }
            if (flag)
                r = mid;
            else l = mid + 1;
        }
        printf("%d\n",r);
    }
    return 0;
}

HDU - 4190 Distributing Ballot Boxes,布布扣,bubuko.com

HDU - 4190 Distributing Ballot Boxes

原文：http://blog.csdn.net/u011345136/article/details/20361749