题目链接
AtCoder Beginner Contest 347
C - Ideal Holidays
思路:
一周有 A + B A+B A+B 天,前 A A A 天放假,问能不能把所有工作放进节假日里。
先看简单的,两个。其实我们并不是很在乎它们中间隔了多少天,我们只在乎前一个工作排在周几的时候,后一个工作排在周几。所以我们可以给两个工作都 模 A + B A+B A+B。而它们之间的差距是不变的(可以想象一个长为 A + B A+B A+B 的一个条带,把两个工作放入相应位置,当前一个工作向后推移一天的时候,后一个工作同样推一天,到结尾后再循环回头部,这两个工作中间的间隔是固定不变的),当我们确定了前一个工作放在周几,后一个工作的时间也就随之确定了。
这个结论可以推广到 n n n 个工作。也就是说,我们只要确定了某个工作放在周几,我们就知道其他工作放在周几了。如果我们想要工作全部落在前 A A A 天里,只需要保证所有工作都落在一个长为 A A A 的连续天数里(还是可以想象成上面的条带,一个工作代表一个点,就是要保证所有点落在一个长为 A A A 的连续长度上)。
我们可以给模完后的工作排个序,然后枚举起点工作,找到最后一个工作落在哪里。也可以枚举相邻的两个工作,看它们之间的间隔是否大于等于 B B B(既然两个工作的间隔天数大于等于 B B B,说明剩下的工作都落在长为 A A A 的连续天数里了)。文章来源:https://www.toymoban.com/news/detail-846979.html
code:
两种写法文章来源地址https://www.toymoban.com/news/detail-846979.html
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;
int n,A,B;
int a[maxn<<1];
bool check(){
for(int i=1;i<=n;i++)
if(a[i+n-1]-a[i]+1<=A)
return true;
return false;
}
int main(){
cin>>n>>A>>B;
int maxx=-1e9,minn=1e9;
for(int i=1,t;i<=n;i++){
cin>>a[i];
a[i]%=(A+B);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)a[i+n]=a[i]+A+B;
puts((check())?"Yes":"No");
return 0;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;
int n,A,B;
int a[maxn];
int main(){
cin>>n>>A>>B;
int maxx=-1e9,minn=1e9;
for(int i=1,t;i<=n;i++){
cin>>a[i];
a[i]%=(A+B);
}
sort(a+1,a+n+1);
bool flag=false;
if(a[1]+A+B-a[n]-1>=B)flag=true;
else for(int i=2;i<=n;i++){
if(a[i]-a[i-1]-1>=B){
flag=true;
break;
}
}
puts((flag)?"Yes":"No");
return 0;
}
到了这里,关于Ideal Holidays的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!