【2016 Asia China-Final D题】

题意：
    现在有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,那么现在一个m要向后找1e2个数,那是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;
            }
            else
                r=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;
//当较小得数不满足得时候，后面较大得那个数对当前得b[i]也是不满足，就缩短时间复杂度了
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;
            }
            else
                r=mid-1;
        }
        printf("Case #%d: %d\n",ca,ans);//cout<<"Case #"<<ca <<": "<<ans<<endl;
    }
    return 0;
}