前置知识：抽屉原理

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

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

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

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

思路

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

再读题，从题目中的“他认为第$i$种颜色必须准确使用$a_i$次，而且每$k$个连续的单元格，它们的颜色必须是不同的。”这句话就可以找到抽屉原理的影子。

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

那么如果有$a_i$($1 \le i \le m)$$>$c,根据上文的抽屉原理可得，至少有 1段的颜色数量$\ge 2$，显然是不符合题目要求的。 如果有$x$个均满足$a_i$ $( 1 \le i \le m)$ $=c$,设最后一段有$y$个格，那如果$x>y$，根据抽屉原理也至少有1段颜色数量 $\ge 2$,也算不符合题目要求的。 除去以上两种不可行的条件外，剩下的就是可行的了。

代码

#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;
}