欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【2016 Asia China-Final D题】

程序员文章站 2024-03-17 16:30:28
...

题意:
    现在有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;
}

 

相关标签: 二分答案