Ideal Holidays_c - ideal holidays(ai)

题目链接

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28