[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

但如果我们假设今天是周一,第一个计划在本周二实现,第二个计划在下周一实现的话,其实是可行的。


为了解决上面的问题,我们要分类讨论一下:

  1. \(sum<=A\) 绝对可以实现,直接输出Yes;

  2. \(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 前辈提供思路。

热门相关:前夫有毒:1000万夺子契约   灭世魔帝   血战天下   北宋大丈夫   豪门24小时:吻别霸道前夫