?

? ? ?顯然答案具有單調(diào)性，可以二分。問題是 我們二分出一個(gè) 堆數(shù)，該怎么判定能否達(dá)到這個(gè)堆數(shù)呢？

? ? 我們可以很簡單的用調(diào)整法證明，最底下的一層的冰淇淋肯定是最小的那些，往上疊加的話我們再貪心的讓較少的放在較小的上面，答案總不會更劣。

? ? 于是就口胡完了2333

?

#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=300005; int T,n,k,now,ans,L,R,mid,pre,N; ll a[maxn],num[2][maxn];inline ll read(){ll x=0; char ch=getchar();for(;!isdigit(ch);ch=getchar());for(;isdigit(ch);ch=getchar()) x=x*10ll+ch-'0';return x; }inline bool can(){N=1,pre=0,now=1;for(int i=1;i<=mid;i++) num[now][i]=a[N++];for(int i=2;i<=k;i++){pre=now,now^=1;for(int j=1;j<=mid;j++){while(N<=n&&a[N]<2ll*num[pre][j]) N++;if(N>n) return 0;num[now][j]=a[N++];}}return 1; }inline void solve(){ans=0,scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) a[i]=read();sort(a+1,a+n+1);L=0,R=n/k;while(L<=R){mid=L+R>>1;if(can()) ans=mid,L=mid+1;else R=mid-1;}printf("%d\n",ans); }int main(){scanf("%d",&T);for(int i=1;i<=T;i++){printf("Case #%d: ",i);solve();}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/JYYHH/p/8867956.html

總結(jié)

以上是生活随笔為你收集整理的The 2016 ACM-ICPC Asia China-Final Contest Promblem D的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。