P9756

tangqianlang · 2023-10-19 22:31:56 · 题解

题意：有 n 张桌子， m 种椅子，第 i 种椅子有 a_i 把。问有没有一种方案能满足每张桌子放 4 把相同颜色的椅子，并且每种椅子都被用过。

通过题目可以得出以下三个结论：

1. 当 m>n 时，不能满足。因为每张桌子只能放一种椅子，当椅子种类比桌子多时，至少有 m-n 种椅子不会被用到。

2. 当 a_i<4 时，不能满足。因为第 i 种椅子放不满一张桌子，所以用过每种椅子。

3. 当能摆满的桌数比 n 小时，不能满足。第 i 种椅子能摆满的桌数为 \lfloor\frac{a_i}{4}\rfloor 。

通过以上结论可以得到代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int a[m];
    for(int i=0;i<m;i++){
        cin>>a[i];
    }
    if(m>n){
        cout<<"NE";
        return 0;
    }
    int cnt=0;
    for(int i=0;i<m;i++){
        cnt+=a[i]/m;
        if(a[i]/m==0){
            cout<<"NE";
            return 0;
        }
    }
    if(cnt<n){
        cout<<"NE";
        return 0;
    }
    cout<<"DA";
    return 0;
}