CF 428 div2 B. Game of the Rows

题目在这里>_<

题意

在飞机上每一排有$8$个座位，座位图在题目链接中。有$n$组人入座飞机，每组有$a_i$个人，相邻的座位上只能坐同一组的人，问是否能让所有人入座。

思路

观察到四连座可以分为一个两人座加一个单人座或者变成两个单人座，两人座可以变成一个单人座。
因此我们可以记录当前有多少单人座，两人座和四连座。

• 因为所有的都可以转换为单人座，所以我们尽量最后为所有的单人分配座位。
• 如果当前有大于等于$4$个人要入座，我们将其分为$4$人一组。显然每组入座四连座是最优的，四人座不够拆开入座两人座是最优的，再不够将其入座单人座。
• 如果$1$人入座，那么显然入座单人座是最优的。其次考虑四人座，因为四人座可以拆成两个单人座，而两人座只能变成一个单人座，会白浪费一个空间。最后考虑两人座。
• 如果有$2$人入座，有两人座直接入座两人座，有四人座拆成两人座加单人座入座，只有单人座就将两人分别入座。
• 如果有$3$人入座，如果有单人座的话，那么最优的是将一个人入座单人座，剩下两个人再入座，否则如果有四连座就入四连座（拆成两人座加四人座的单座与其等价，所以不需考虑），否则拆开入座两人座。

这题的hack数据居然把标程hack掉了，害得出题人另写了标程，导致比赛过了很久才开始判分233333

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=1e6+7;
typedef long long ll;
int n,k;
int four,two,one;
int push(int x)
{
    if(x>=4)
    {
        four-=x/4;
        x%=4;
    }
    if(four<0)
    {
        two+=2*four;
        four=0;
        if(two<0)
        {
            one+=two*2;
            two=0;
            if(one<0)
                return 0;
        }
    }
    if(x==0)
        return 1;
    if(x==1)
    {
        if(one)
            one--;
        else if(four)
        {
            four--;
            two++;
        }
        else if(two)
            two--;
        else
            return 0;
    }
    else if(x==2)
    {
        if(two)
            two--;
        else if(four)
        {
            four--;
            one++;
        }
        else if(one>=2)
            one-=2;
        else
            return 0;
    }
    else if(x==3)
    {
        if(one)
        {
            one--;
            if(!push(2))
                return 0;
        }
        else
        {
            if(four)
                four--;
            else if(two>=2)
                two-=2;
            else 
                return 0;
        }
    }
    return 1;    
}
int main()
{
    #ifdef test
    #endif
    //freopen("b.in","r",stdin);
    scanf("%d%d",&n,&k);
    four=n;
    two=2*n;
    one=0;
    int cnt=0;
    while(k--)
    {
        static int x;
        scanf("%d",&x);
        if(x==1)
        {
            cnt++;
            continue;
        }
        int flag=push(x);

        //printf("push(%d):%d\n",x,flag);
        if(!flag)
            return 0*printf("NO\n");
    }
    while(cnt--)
        if(!push(1))
            return 0*printf("NO\n");
    printf("YES\n");
    return 0;
}