Input file: Standard Input
Output file: Standard Ouptut
Time limit: 6 seconds
接着整理奥，2016 ACM-ICPC Asia China-Final的D题。
题目大意：输入n和k，给出n个ice cream balls的大小，k个balls可以组成一个Tower，且里面每下面一层ball的大小>=2*上面一层ball的大小，
求最多能组成几个Towers。
一开始想的只有贪心：从最大的ball开始找，找到一个就加上，尽量剩下小的，可以更好组成Towers。
结果还需要二分，而且一开始的想法也不太对(至于为什么我也不太清楚..菜鸡哭了)，是先贪小的，在1到n里随机取1个数，作为求解的结果num，将所有小的作为num个Tower的顶层，然后
往下加层数，直到k层。然后不断二分查找到最大的num值就可以了。
代码如下：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 int T,n,k,cas=1; 6 long long a[300005],ceng[300005];//二分+贪心 7 bool isvalid(int b) 8 { 9 int i=0; 10 for(i=0; i<b; i++) 11 ceng[i]=a[i];//当前层的每个的大小 12 for(int j=1; j<k; j++)//对于除了第一层的剩余k-1层 13 for(int p=0; p<b; p++) 14 { 15 while(a[i]<2*ceng[p]) 16 { 17 i++; 18 if(i>=n) 19 return false; 20 } 21 ceng[p]=a[i]; 22 i++; 23 } 24 return true; 25 } 26 int main() 27 { 28 cin>>T; 29 while(T--) 30 { 31 memset(a,0,sizeof(a)); 32 memset(ceng,0,sizeof(ceng)); 33 cin>>n>>k; 34 for(int i=0; i<n; i++) 35 cin>>a[i]; 36 if(k==1) 37 { 38 cout<<"Case #"<<cas++<<": "<<n<<endl; 39 continue; 40 } 41 sort(a,a+n); 42 int star=0,endd=n+1; 43 while(endd-star>1)//二分查找 44 { 45 int mid=(star+endd)/2; 46 if(isvalid(mid)) 47 star=mid; 48 else 49 endd=mid; 50 } 51 cout<<"Case #"<<cas++<<": "<<star<<endl; 52 } 53 return 0; 54 }
原文：https://www.cnblogs.com/shangqing/p/11255582.html