CF1774B Coloring
题意
Cirno_9baka 的纸条上有 \(n\) 个格子，他觉得空白的纸条看着有点无趣，于是想在纸条的格子上涂上 \(m\) 种颜色。同时，他认为第 \(i\) 种颜色必须要用 \(a_i\) 次，且每连续 \(k\) 个格子里涂的颜色必须互不相同。
Cirno_9baka 想知道有没有这样的一种涂色方案能符合他的要求。
思路
我们可以将其看作是将长度为\(n\)的纸条每\(k\)个为一个周期，那很明显，一种颜色最多出现的次数就是\(\lfloor \frac{n}{k} \rfloor\)
而，有一部分多出来的，也就是说有一些颜色会出现的比\(\lfloor \frac{n}{k} \rfloor\)多\(1\)，这些颜色共有\(n-n\times \lfloor \frac{n}{k} \rfloor\)种。
那么，过程中就只用判断是否有颜色多于\(\lfloor \frac{n}{k} \rfloor\)，以及出现\(\lfloor \frac{n}{k} \rfloor +1\)次的颜色数量是否满足要求即可
代码
又是分支语句切1500的一天
#include<bits/stdc++.h>
using namespace std;
int n,m,k,t,maxn,num,ans;
void run()
{
cin>>n>>m>>k;maxn=n/k;num=n-maxn*k;ans=1;
for(int i=1;i<=m;i++)
{
cin>>t;
if(t==maxn+1) num--;
if(t>maxn+1 || num<0) ans=0;
}
cout<<(ans?"Yes":"No")<<endl;
return;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--) run();
system("echo. & pause");
return 0;
}
但是有个很奇妙的一点，如果在6，7行中间插入这个：
if(m<k)
{
cout<<"No"<<endl;
return;
}
我的代码就能从\(63\)ms直线上升到TLE
就为了这个我交了将近10次（悲