Ideal Holidays

题目链接

AtCoder Beginner Contest 347

C - Ideal Holidays

---

思路：

一周有 $A+B$ 天，前 $A$ 天放假，问能不能把所有工作放进节假日里。

先看简单的，两个。其实我们并不是很在乎它们中间隔了多少天，我们只在乎前一个工作排在周几的时候，后一个工作排在周几。所以我们可以给两个工作都 模 $A+B$。而它们之间的差距是不变的（可以想象一个长为 $A+B$ 的一个条带，把两个工作放入相应位置，当前一个工作向后推移一天的时候，后一个工作同样推一天，到结尾后再循环回头部，这两个工作中间的间隔是固定不变的），当我们确定了前一个工作放在周几，后一个工作的时间也就随之确定了。

这个结论可以推广到 $n$ 个工作。也就是说，我们只要确定了某个工作放在周几，我们就知道其他工作放在周几了。如果我们想要工作全部落在前 $A$ 天里，只需要保证所有工作都落在一个长为 $A$ 的连续天数里（还是可以想象成上面的条带，一个工作代表一个点，就是要保证所有点落在一个长为 $A$ 的连续长度上）。

我们可以给模完后的工作排个序，然后枚举起点工作，找到最后一个工作落在哪里。也可以枚举相邻的两个工作，看它们之间的间隔是否大于等于 $B$（既然两个工作的间隔天数大于等于 $B$，说明剩下的工作都落在长为 $A$ 的连续天数里了）。

code：

两种写法

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