• 前言
• 题目大意
• 思路
• 代码
• 总结

前言

总结了一种新的贪心思路

题目大意

题面有点长扔个链接QWQ

思路

由于中间的两个椅子（看成四人座）占得人比较多，所以先把这个椅子坐满肯定很好，因为除了中间都不跟人触碰。我们把中间的全放上一个队。放到不能放为止。这样的四人座有 $n$ 个。

之后比较优秀的是二人座，因为可以容纳两名一个队的人。这样的座位原本有 $2\times n$ 个，但因为有可能四人座没做完，加上剩余的四人座个数即可。

最后把剩余的算成单人座即可。也就是剩余的前两个座位的个数个。

代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;
const ll MAXN = 1e4 + 5;
ll n, k, a[MAXN];

int main() {
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= k; ++i) {
        scanf("%lld", &a[i]);
    }
    ll four = n;
    for (int i = 1; i <= k; ++i) {
        ll num = min(four, a[i] / 4);//有这么多的空位要做或者可以做
        four -= num;//四人座座位减掉这些
        a[i] -= num * 4;//每个座位可以做4个人，所以减掉座位数乘以4
    }
    //二人座同上
    ll two = 2 * n + four;
    for (int i = 1; i <= k; ++i) {
        ll num = min(two, a[i] / 2);
        two -= num;
        a[i] -= num * 2;
    }
    ll left = two + four;//剩余（单人座）
    for (int i = 1; i <= k; ++i) {
        left -= a[i];
        if (left < 0) {
            printf("NO\n");//座位数小于0了就不行了
            return 0;
        }
    }
    printf("YES\n");//否则可以
    return 0;
}

总结

这种贪心方法我管它叫“榨汁算法”，也就是优先选用“汁”最多的榨，这样可以先减少最多的“水果”，之后汁越来越少，但是水果减缓的数量也变慢了。在本题“汁”最多的是四人座，其次二人座，最后单人座。可以根据这个来思考。