CF1774B 题解

· · 题解

前铺知识：抽屉原理

抽屉原理大家都不陌生，这个知识也出现在了小学课本上，小学六年级下册数学书中称其为“鸽巢原理”，但都是一样的。

例：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，都会发现至少有一个抽屉里面放不少于两个苹果。

即当 m\le n 时，把 n+m 个苹果放进 n 个抽屉里，至少有 1 个抽屉里面放的苹果数 \ge 2。

由此可继续推出把 kn+m 个苹果放进 n 个抽屉里，至少有 1 个抽屉里面放的苹果数 \ge k+1。

思路

那么如何将上面讲的抽屉原理运用到本题中呢？

再读题，从题目中的“同时，他认为第 i 种颜色必须要用 a_i 次，且每连续 k 个格子里涂的颜色必须互不相同”这句话就可以找到抽屉原理的影子。

首先读完题后第一个想到的就是求段数（格数），即段数 c=\frac{n}{k}。

那么如果有 a_i(1\le i\le m) > c，根据上文的抽屉原理可得，至少有 1 段的颜色数量 \ge2，显然是不符合题目要求的。

如果有 x 个 i 均满足 a_i(1\le i\le m) = c，设最后一段有 y 个格，那如果 x>y，根据抽屉原理也至少有 1 段的颜色数量 \ge2，也是不符合题目要求的。

除去以上两种不可行条件外，剩下的就是可行的啦。

代码

#include<bits/stdc++.h>
using namespace std;
int a[100001];
int main(){
    int n, m, t, k;
    cin >> t;
    while(t--){
        cin >> n >> m >> k;
        int c = ceil(n*1.0/k);
        int cnt = 0;
        bool flag = true;
        for(int i = 1;i <= m;i++){
            cin >> a[i];
            if(a[i] > c){
                flag = false;
            }
            if(a[i] == c){
                cnt++;
            }
        } 
        if(!flag){
            cout << "NO" << endl;
        }else if(cnt > (n-1)%k+1){
            cout << "NO" << endl;
        }else{
            cout << "YES" << endl;
        }
    }
    return 0;
}