(贪心)

题意：

有k种颜色，每种有\(a_i\)个，将这k种颜色放在一个\(n * 8格子里\)

放置规则不能出现两个不同颜色在相邻的格子里，相邻的定义为在同一行

出现在(1,2),(3,4),(4,5),(5,6)或者(7,8) 这样都算相邻

\(1 <= n <= 10000\)

\(a_i <= 1000\)

$ \sum a_i <= 8 * n$

思路:

这道题贪心很不错，我是yy了很久了

贪心策略应该是让每种颜色尽量填满中间，再填满两边，

然后再把三个的放到中间，放不下就放到两边，

再把两个的放到中间，最后再填一个的

#include
    
     #define LL long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define ls (rt<<1)#define rs (rt<<1|1)using namespace std;const int N = 1e6 + 10;const int M = 1e6 + 10;const int mod = 1e9 + 7;int a[1100];void can(int &x,int &y,int d){    if(!x || y < d) return ;    int res = min(x, y / d);    x -= res;    y -= res * d;}int main(){    int n,k;    cin>>n>>k;    int cnt2 = 2 * n,cnt4 = n;    for(int i = 0;i < k;i++){        scanf("%d",a + i);    }    for(int i = 0;i < k;i++){ ///首先尽量填满中间，然后填满两边        can(cnt4,a[i],4);        can(cnt2,a[i],2);        if(a[i] && (!cnt2 && !cnt4)) {            puts("NO");            return 0;        }    }    int c[4] = {0};    for(int i = 0;i < k;i++) c[a[i]]++;    int res3 = min(cnt4,c[3]);///把 3的 尽量放中间    c[3] -= res3;    cnt4 -= res3;    if(2 * c[3] > cnt2){ ///剩下的3 只能放两边了        puts("NO");        return 0;    }    cnt2 -= 2 * c[3];    int res2 = min(cnt4,c[2]); ///将 2 个的 放在中间的 剩余一个位置可以放其他    c[2] -= res2;    cnt4 -= res2;    if(2 * c[2] + c[1] <= res2 + cnt4 * 2 + cnt2) puts("YES");///计算所有能放一个的不同位置的个数    else puts("NO");    return 0;}