題意：
? ? 現(xiàn)在有n個蛋糕值,要求把n個蛋糕值摞起來,螺成k層,而每一層得蛋糕值至少是上一層蛋糕值得2倍，求最后最多可以螺成幾個蛋糕.
? ? 例如第一個樣例
? ? ?1 2 3 4 ?要成2層，那么有(1 3) (2 4)所以最多可以形成2個
? ? ?思路是二分枚舉最多可以成為多少個
? ? ?然后看最這個是否滿足有k層得這些個
? ? ?自己再找是否有k個可以滿足得時候，完美的寫的超時了,看代碼吧

T掉的：
?

#include<bits/stdc++.h> #define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <iostream> #include <cmath> #include <cstdio> #include <stdlib.h> #include <ctime> using namespace std; typedef long long ll; typedef pair<int,int> PII; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e6 + 5; int cnt=0; int cnt1=0; ll b[maxn]; ll a[maxn]; int vis[maxn]; int k,n; int work(int m) {for(int i=0;i<m;++i)a[i]=b[i];for(int p=1; p<k; ++p){for(int i=0; i<m; ++i){// 1、//int pos=lower_bound(b+m*p,b+n,a[i]*2)-b;//cout<<'s'<<pos<<endl;//2、 md，找bug能力,分析能力不行啊,在這兒如果m是1e3,那么現(xiàn)在一個m要向后找1e2個數(shù),那是1e2個1e3得次方啊。/*int pos=0;for(int j=m*p;j<n;++j){if(b[j]>=2*a[i]){pos=j;break;}}*/if(pos==0)return 0;if(vis[pos]==0) vis[pos]=1,a[i]=b[pos];//,cout<<'p'<<pos<<' ';else{int j;for( j=pos+1; j<n; ++j)if(vis[j]==0){vis[j]=1;a[i]=b[j];break;}if(j==n)return 0;}}}return 1; } int main() {IO;int t;scanf("%d",&t);//cin>>t;for(int ca=1; ca<=t; ++ca){scanf("%d%d",&n,&k);//cin>>n>>k;for(int i=0; i<n; ++i) scanf("%lld",&b[i]);sort(b,b+n);int ans=0;int r=n;int l=0;int mid;while(l<=r){mid=l+(r-l)/2;memset(vis,0,sizeof(vis));if(work(mid)){ans=mid;l=mid+1;}elser=mid-1;}printf("Case #%d: %d\n",ca,ans);//cout<<"Case #"<<ca <<": "<<ans<<endl;}return 0; }

正解：

#include<bits/stdc++.h> #define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <iostream> #include <cmath> #include <cstdio> #include <stdlib.h> #include <ctime> using namespace std; typedef long long ll; typedef pair<int,int> PII; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e6 + 5; int cnt=0; int cnt1=0; ll b[maxn]; ll a[maxn]; int vis[maxn]; int k,n; //當(dāng)較小得數(shù)不滿足得時候，后面較大得那個數(shù)對當(dāng)前得b[i]也是不滿足，就縮短時間復(fù)雜度了 int work(int m) {for(int i=0;i<m;++i)a[i]=b[i];int pos=m;for(int i=m;i<m*k;++i){while(b[pos]<a[i-m]*2&&pos<n)pos++;if(pos==n)return 0;a[i]=b[pos];pos++;}return 1; } int main() {// IO;int t;scanf("%d",&t);//cin>>t;for(int ca=1; ca<=t; ++ca){scanf("%d%d",&n,&k);//cin>>n>>k;for(int i=0; i<n; ++i) scanf("%lld",&b[i]);sort(b,b+n);int ans=0;int r=n;int l=0;int mid;while(l<=r){mid=l+(r-l)/2;memset(vis,0,sizeof(vis));if(work(mid)){ans=mid;l=mid+1;}elser=mid-1;}printf("Case #%d: %d\n",ca,ans);//cout<<"Case #"<<ca <<": "<<ans<<endl;}return 0; }

?

總結(jié)

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

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