题解：AT_abc480_c [ABC480C] Self-Stopping Shower

· · 题解

前言

没打比赛，写篇题解玩玩。

思路

注意到题目本质上就是一个贪心的区间覆盖问题，也就是给定几个区间（左端点为 a_i，右端点为 a_i+k），然后可以自己添加区间去覆盖 [0, T] 这个大区间。

我们可以将 a_i 从小到大排序，接着定义变量 last 来代表当前能够覆盖的最远的时刻。然后在 a_i 小于 last 中选择一个最大的 a_i，并将 last 赋值为 a_i+k（好好想想为什么）。如果没有 a_i<last 才自己按（能白嫖就白嫖）。

思路给完了，建议自己先试着写一遍，如果不会的话再看下面的代码哦！

AC code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
int a[MAXN];
int n,k,t;

int main(){
    scanf("%d%d%d",&n,&k,&t);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int last=0,j=1;
    int ans=0;
    while(last<t){
        int tmp=last;
        while(j<=n&&a[j]<=last){
            tmp=max(tmp,a[j]+k);
            j++;
        }
        if(last==tmp){
            ans++;
            last+=k;
        }
        else last=tmp;
    }
    printf("%d",ans);
    return 0;
}

题解不易，祝所有点赞的同学们运气爆表并 AK 接下来的 CSP-J/S，以及每一场比赛！！！谢谢啦 qwq。

The End