[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 前辈提供思路。