[ABC347C] Ideal Holidays题解
[ABC347C] Ideal Holidays题解
题意翻译：
在 \(AtCoder\) 王国中，一个周有 \(A+B\) 天。其中在一周中， \([1,A]\) 天是假日， \([A+1,B]\) 天是工作日。
高桥有 \(N\) 个计划，第 \(i\) 个计划安排在 \(i\) 天后。他不知道今天是周几，但他想知道是否能将计划都安排在假期中；
若可以则打印Yes,否则打印No。
题意解释：
如下图，黄绿色的是假期，红色的是假期。
高桥的安排在这个区间中，对此我们可以进行一个状态压缩，也就是把所有的天数对 \(A+B\) 取模，压缩到一个周内；
即：
int sum=a+b; //存储A+B
for(int i=1;i<=n;i++){
scanf("%d",d[i]); //输入
d[i]%=sum; //压缩到一周内
}
若有大于 \(A\) 的，便输出No ,于是我们可以写出第一版代码：
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 2e5+10;
ll n,a,b,sum,num;
ll d[maxn];
signed main()
{
scanf("%lld",&n);
scanf("%lld%lld",&a,&b);
sum=a+b;
seq(i,1,n){
scanf("%lld",&num);
d[i]=num%sum;
}
seq(i,1,n){
if(d[i]>a){
printf("No");
return 0;
}
}
printf("Yes");
return 0;
}
但是会发现错的有点多，这是为啥呢？
我们可以看到，由于高桥不知道今天是周几，所以直接比较行不通。
于是我们想到第二种思路：
用其中最大值减最小值，即求一个区间，看这个区间是否在 \(A\) 以内即可。
即可写出第二版代码：
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 2e5+10;
ll n,a,b,sum,num;
ll d[maxn];
signed main()
{
scanf("%lld",&n);
scanf("%lld%lld",&a,&b);
sum=a+b;
seq(i,1,n){
scanf("%lld",&num);
d[i]=num%sum;
}
sort(d+1,d+1+n);
num=d[n]-d[1]+1; //区间值
if(num>a){ //区间不在A之内
printf("No");
return 0;
}
printf("Yes");
return 0;
}
但还是会错一个点，这又是为啥呢？
因为如果其跨度超过 \(B\) 我们可以放到下周去做。
如： 使 \(A=2，B=5，N=2，D[]=\{1,7\}\) 对与我们第二种做法，区间值应为 \(7\) ，\(7>A(2)\) ,应输出No。
但如果我们假设今天是周一，第一个计划在本周二实现，第二个计划在下周一实现的话，其实是可行的。
为了解决上面的问题，我们要分类讨论一下：
-
\(sum<=A\) 绝对可以实现，直接输出
Yes; -
\(sum>A\) :
1.若相邻两个元素的差有一个大于 \(B\) 则可以实现，直接输出
Yes； (按大小排序，且区间在 \([A,A+B]\) 之间，如果有一个差大于 \(B\) ，则后面的元素于此元素的差都大于 \(B\) )
2.若相邻两个元素的差都小于 \(B\) 则不可以实现，输出
No；
根据上面的分析，我们可在二思路上改进一下，即可得出正确代码：
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 2e5+10;
ll n,a,b,sum;
ll d[maxn];
signed main()
{
scanf("%lld",&n);
scanf("%lld%lld",&a,&b);
sum=a+b;
seq(i,1,n){
scanf("%lld",&d[i]);
d[i]%=sum;
}
sort(d+1,d+1+n);
sum=d[n]-d[1]+1;
if(sum>a){ //区间不在A之内
seq(i,1,n-1){
if(d[i+1]-d[i]-1>=b){ //若有一个差大于B
printf("Yes");
return 0;
}
}
printf("No");
return 0;
}
printf("Yes");
return 0;
}
总的来说，本题对做题者的细心程度非常考察，本蒟蒻在做时吃了九遍罚时，在此感谢 @LiJoQiao 前辈提供思路。