P9756 题解

FurippuWRY · 2023-10-17 18:56:42 · 题解

思路：因为一张桌子需要 4 把椅子，所以第 i 种颜色的椅子一共会摆出 \left\lfloor\dfrac{a_i}{4}\right\rfloor 把。但注意到：

• 每张桌子的椅子颜色需要相同
• 每种颜色的椅子至少有一张桌子用到了

当 a_i < 4 时，无法安排椅子，输出 NE。

而且根据上述两点可以推出，当 n < m 时，也同样无法安排椅子，这种情况也输出 NE。

以及还有一点情况：放不满，这种情况下用一个变量 ans = 0，对于不同的 i，ans\leftarrow ans + a_i，如果加完了之后 ans < n，则意味着放不满，输出 NE。

如果上述情况都不满足，输出 DA 就行了。

#include <bits/stdc++.h>

using namespace std; 

const int N = 1145141;

int n, m, a[N], ans;

int main(){
    cin >> n >> m;
    if (n < m) {
        puts("NE");
        return 0;
    }
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
        if (a[i] < 4) {
            puts("NE");
            return 0;
        }
        ans += a[i] / 4;
    }
    if (ans < n) {
        puts("NE");
        return 0;
    }
    puts("DA");
    return 0;
}