來源于： http://hi.baidu.com/dlutnocow/blog/item/3a23c5ab17de8abccb130c31.html

hdu 3418 二分 湊 ★★★
這題我做不出，看edward_mj的
edward_mj那里也有一種不是二分的，就是每次不斷計算平均值，對于cnt[i]>avg的，cnt[i]=avg（去掉多余的物品）
直到沒有多余的物品。
/*
    題意：n種物品，每種個數為cnt[i],一個人獲得至少m種才算開心，問能是多少人開心
    主要思路是將n種物品壓縮成m種（m<=n），答案就是最少的那種最大化
    
    二分答案limit
    對于每個cnt[i],如果大于limit，取為limit
    最后將這n個cnt[i]累加到sum,判斷sum是否≥limit*m
    (大概就是多余的不要，少的湊一下，看能不能使最少的那個>=limit)
*/
#include<cstdio>
#include<algorithm>
using namespace std;

const long long INF = 1LL<<50;//太大的話*100會溢出！！

int cnt[105];
int n,m;

bool chk(long long x)
{
    long long sum = 0;
    for(int i=0;i<n;i++)
        sum+=min((long long)cnt[i],x);
    return sum>=x*m;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0;i<n;i++)
            scanf("%d",&cnt[i]);
        long long left = 0,right = INF;
        while(right-left>1)
        {
            long long mid = (right+left)>>1;
            if(chk(mid))left=mid;
            else right=mid;
        }
        printf("%I64d\n",left);            
    }    
    return 0;
}


zoj 3334  ★★★
也即求能使m個醫生同時工作的最長時間
類似于湊，將n種湊成m種，使最短的那個最長
/*
    題意：m個醫生檢查n個病人，每個病人需要時間為t[i] 
           每個病人可以分為多次檢查，每次一個醫生  但不能同時被多個醫生檢查
           對于醫生，要么m個同時工作，要么只有1個工作   求最少的檢查時間
    當然，能m個醫生同時檢查的先同時檢查
    而求n個人能被m個醫生同時檢查的最長時間跟hdu3418類似
    使湊成m個的最少的那個最長！

    二分枚舉時間limit
    時間大于limit的變為limit
    累加總時間，看是否≥limit*m

    然后剩余的只能一個醫生工作了
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const double EPS = 1e-12;
const int MAXN = 1005;

double t[MAXN];
int n,m;

bool chk(double limit)
{
    double sum=0.0;
    for(int i=0;i<n;i++)
        sum+=min(limit,t[i]);
    return sum>limit*m-EPS;//>=
}
double cal(double tot)//計算能被m個醫生同時檢查的最長時間
{
    if(m>n)return 0.0;

    double left = 0,right = tot;
    for(int i=0;i<60;i++)
    //while(right-left>EPS)  -->  TLE
    {
        double mid=(left+right)/2.0;
        if(chk(mid))left=mid;
        else right=mid;
    }
    return left;
}
int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        double tot = 0.0;
        for(int i=0;i<n;i++)
        {
            scanf("%lf",&t[i]);
            tot+=t[i];
        }
        printf("%.4f\n",tot-(m-1)*cal(tot));
    }
    return 0;
}


hdu 2730
/*
    題意： 一個工具箱里有n種顏色，每種50ml 。而任意三種數量為x顏色
        mix能湊出數量x的灰色   現給出每種顏色的還有灰色的需求量  
        求最少需要購買的工具箱  跟hdu 3418類似

    可二分枚舉工具箱的個數
    然后再檢查能否滿足各種顏色，還有灰色的數量需求

*/
#include<cstdio>
#include<algorithm>

using namespace std;

const int INF = 10000000;

int cnt[15],_cnt[15];
int n,gray;

bool _chk(int limit)
{
    int sum = 0;
    for(int i=0;i<n;i++)
        sum+=min(limit,_cnt[i]);
    return sum>=limit*3;
}

int cal()
{
    int left = 0,right = INF;
    while(right-left>1)
    {
        int mid=(right+left)>>1;
        if(_chk(mid))left=mid;
        else right=mid;
    }
    return left;
}

bool chk(int x)
{
    for(int i=0;i<n;i++)
    {
        _cnt[i]=50*x-cnt[i];
        if(_cnt[i]<0)return false;
    }
    return cal()>=gray;
}

int main()
{
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    while(scanf("%d",&n),n)
    {
        for(int i=0;i<n;i++)
            scanf("%d",&cnt[i]);
        scanf("%d",&gray);
        int low = -1 , high = INF;//low=-1    high=0也可以取到
        while(high-low>1)
        {
            int mid=(high+low)>>1;
            if(chk(mid))high = mid;
            else low = mid;
        }
        printf("%d\n",high);
    }
    return 0;
}