CF1774B-Coloring 题解

· · 题解

我非常喜欢吸氧。

正文

这道题是一个不用吸氧的关于鸽笼原理的题目，所谓鸽笼原理，又称抽屉原理，就是说把 n+1 只鸽子放进 n 个铁笼中，则至少有一个铁笼中的鸽子数量 大于 2。

根据鸽笼原理，我们可以找出在本题里的“铁笼数”\lceil\dfrac{n}{k}\rceil，而每个笼子的容积我们也能确定，除最后一个笼子的容积可能为 n\bmod k 之外，剩下的都是 k。这道题我们就可以转化成，在 \lceil\dfrac{n}{k}\rceil 个铁笼里放上不超过其容积的一些不同种类鸽子，且每个笼子里不能有相同种类的鸽子，是否有这样的方案。

之后我们就来判断能否装下所有鸽子了。容易发现，如果 a_i\gt\lceil\dfrac{n}{k}\rceil，说明必须有一些笼子盛放两个同样的鸽子，则无法满足“每个笼子里不能有相同种类的鸽子”的条件，说明无法满足条件。

继续进行分析，发现有可能会有 a_i=\lceil\dfrac{n}{k}\rceil 的情况，那么每个笼子里都会有一只第 i 种鸽子。根据之前的分析，我们可以发现前面笼子的容积总是会大于等于最后一个笼子的容积，那我们只要看最后一个笼子的容积能否装下这些满足条件的 a_i 数量好了。最后一个笼子的容积为 n\bmod k，如果满足条件的 a_i 数量超过了最后一个笼子的容积，则最后一个笼子无法装下这么多的鸽子，说明无法满足条件。

当然，在上面的分析中，我们说的是最后一个笼子的容积可能为 n\bmod k，而如果 n\bmod k=0，说明最后一个笼子的容积是 0，但这样的话相当于没有这个笼子，所以顺延下来最后一个笼子的容积应该是 k，我们可以用一个三目运算符来表示： n%k==0?k:n%k。

否则，说明一定能装下这些鸽子。

AC C++ CODE:

#include<bits/stdc++.h>
using namespace std;
int a[100001];
int main(){
    int t,n,m,k,tot=0;
    bool f=0;
    cin>>t;
    while(t--){
        cin>>n>>m>>k;
        for(int i=1;i<=m;i++){
            cin>>a[i];
            if(a[i]>ceil(n*1.0/k))f=1;
            else if(a[i]==ceil(n*1.0/k))tot++;
        }
        if(f||tot>(n%k==0?k:n%k))cout<<"NO\n";
        else cout<<"YES\n";
        tot=f=0;
    }
    return 0;
}

完结撒花！

By ImNot6Dora