30分模拟+贪心
查看原帖
30分模拟+贪心
61017
Idoyt楼主2018/10/8 16:28

第二个测试点的第12组数据一直过不去2333

#include<bits/stdc++.h>
using namespace std;
int pa[20];
bool dan[20],shuang[20],san[20],zhadan[20];
int T,n,ans;
void danshunzi()
{
    for(int i=3;i<=14;i++)
    {
        if(pa[i]<1)continue;
        int cnt=0,now=0;
        for(int j=i+1;j<=14;j++)
        {
            if(pa[j]<1)break;
            cnt++;
            if(cnt>=4)now=j;
        }
        if(cnt>=4)
        {
            for(int j=i;j<=now;j++) pa[j]--;
            ans++;
        }
    }
}
void shuangshunzi()
{
    for(int i=3;i<=14;i++)
    {
        int cnt=0,now=0;
        if(pa[i]<2)continue;
        for(int j=i+1;j<=14;j++)
        {
            if(pa[j]<2)break;
            cnt++;
            if(cnt>=2)now=j;
        }
        if(cnt>=2)
        {
            ans++;
            for(int j=i;j<=now;j++)pa[j]-=2;
        }
    }
}
void sanshunzi()
{
    for(int i=3;i<=14;i++)
    {
        int cnt=0,now=0;
        if(pa[i]<3)continue;
        for(int j=i+1;j<=14;j++)
        {
            if(pa[j]<3)break;
            cnt++;
            if(cnt>=1)now=j;
        }
        if(cnt>=1)
        {
            ans++;
            for(int j=i;j<=now;j++)pa[j]-=3;
        }
    }
}
void danpa()
{
    int l1=0,l2=0,l3=0,l4=0;
    for(int i=3;i<=15;i++)
    {
        if(pa[i]==1)l1++;
        if(pa[i]==2)l2++;
        if(pa[i]==3)l3++;
        if(pa[i]==4)l4++;
    }
    //printf("%d %d %d %d\n",l1,l2,l3,l4);
    if(l4>0)
    {
        while(l4>0)
        {
            if(l1<2)break;
            l1-=2;ans++;l4--;
        }
    }
    if(l4>0)
    {
        while(l4>0)
        {
            if(l2<2)break;
            l2-=2;ans++;l4--;//cout<<"嘤嘤嘤";
        }		
    }
    if(l4>0)ans+=l4;
    if(l3>0)
    {
        while(l3>0)
        {
            if(l2<1)break;
            l2--;
            ans++;
            l3--;
        }
    }
    if(l3>0)
    {
        while(l3>0)
        {
            if(l1<1)break;
            l1--;ans++;l3--;
        }
    }
    if(l3>0)ans+=l3;
    //printf("%d %d %d %d\n",l1,l2,l3,l4);
    ans+=l2;
    ans+=l1;
    //cout<<ans<<endl;
}
int main()
{
    //freopen("ddz.out","w",stdout);
    scanf("%d%d",&T,&n);
    while(T--)
    {
        memset(pa,0,sizeof(pa));
        memset(dan,0,sizeof(dan));
        memset(shuang,0,sizeof(shuang));
        memset(san,0,sizeof(san));
        memset(zhadan,0,sizeof(zhadan));
        int king=0;ans=0;
        for(int i=1;i<=n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a==0)king++;
            if(a==1||a==2)pa[a+13]++;
            else pa[a]++;
        }
        if(king!=0)ans++;
        //for(int i=3;i<=15;i++)printf("%d ",pa[i]);printf("\n");
        danshunzi();
        //for(int i=3;i<=15;i++)printf("%d ",pa[i]);printf("\n");
        shuangshunzi();
        //for(int i=3;i<=15;i++)printf("%d ",pa[i]);printf("\n");
        sanshunzi();
        //for(int i=3;i<=15;i++)printf("%d ",pa[i]);printf("\n");
        danpa();
        //for(int i=3;i<=15;i++)printf("%d ",pa[i]);printf("\n");
        printf("%d\n",ans);
    }
    
    return 0;
}
2018/10/8 16:28
加载中...