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

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

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

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個(gè)醫(yī)生同時(shí)工作的最長(zhǎng)時(shí)間
類似于湊，將n種湊成m種，使最短的那個(gè)最長(zhǎng)
/*
    題意：m個(gè)醫(yī)生檢查n個(gè)病人，每個(gè)病人需要時(shí)間為t[i] 
           每個(gè)病人可以分為多次檢查，每次一個(gè)醫(yī)生  但不能同時(shí)被多個(gè)醫(yī)生檢查
           對(duì)于醫(yī)生，要么m個(gè)同時(shí)工作，要么只有1個(gè)工作   求最少的檢查時(shí)間
    當(dāng)然，能m個(gè)醫(yī)生同時(shí)檢查的先同時(shí)檢查
    而求n個(gè)人能被m個(gè)醫(yī)生同時(shí)檢查的最長(zhǎng)時(shí)間跟hdu3418類似
    使湊成m個(gè)的最少的那個(gè)最長(zhǎng)！

    二分枚舉時(shí)間limit
    時(shí)間大于limit的變?yōu)閘imit
    累加總時(shí)間，看是否≥limit*m

    然后剩余的只能一個(gè)醫(yī)生工作了
*/
#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)//計(jì)算能被m個(gè)醫(yī)生同時(shí)檢查的最長(zhǎng)時(shí)間
{
    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
/*
    題意： 一個(gè)工具箱里有n種顏色，每種50ml 。而任意三種數(shù)量為x顏色
        mix能湊出數(shù)量x的灰色   現(xiàn)給出每種顏色的還有灰色的需求量  
        求最少需要購買的工具箱  跟hdu 3418類似

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

*/
#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;
}