来源于： 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;
}