2016-2017 ACM-ICPC CHINA-Final Ice Cream Tower 二分+贪心

/**
题目：2016-2017 ACM-ICPC CHINA-Final Ice Cream Tower
链接：http://codeforces.com/gym/101194
题意：给n个木块，堆一个小塔要k个木块，满足相邻两个木块，上面的木块大小至少是下面的木块的两倍。
问最多可以堆出几个小塔。

思路：二分+贪心。 先二分最终可以堆出的小塔数x，然后确定了数量，就可以这样来贪心，把前x个木块作为所有小塔的顶部木块，
然后从剩下的木块中继续取前x小的，从小到大放在x个小塔的次顶部，然后继续。。。如果可以取到k层。那么该方案有解。找一个最大的二分结果即可。


*/

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
typedef pair<int,int> P;
typedef __int64 LL;
const int N = 3e5+10;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
LL b[N], a[N];
int n, k;
bool ok(int x)
{
    for(int i = 0; i < x; i++){
        a[i] = b[i];
    }
    int as, bs;
    as = bs = x;
    for(int i = 1; i <= (k-1)*x; i++){
        while(bs<n&&b[bs]<2*a[as-x]){bs++;}
        if(bs==n) return false;
        a[as++] = b[bs++];
    }
    return true;
}
int solve()
{
    int lo = 0, hi = n/k, mi;
    int ans;
    while(lo<=hi){
        mi = (lo+hi)/2;
        if(ok(mi)){
            //cout<<"mi = "<<mi<<endl;
            ans = mi;
            lo = mi+1;
        }else
        {
            hi = mi-1;
        }
    }
    return ans;
}
int main(void)
{
    int T;
    int cas = 1;
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&k);
        for(int i = 0; i < n; i++){
            scanf("%I64d",&b[i]);
        }
        sort(b,b+n);
        printf("Case #%d: %d
",cas++,solve());
    }
    return 0;
}