题解：AT_abc480_c [ABC480C] Self-Stopping Shower 2026.10.19

shuxuejitui · 2026-10-19 14:00:14 · 题解

题意

高桥现在要洗澡，别人会在不同的时间分别按下热水按钮，共按 n 次，并且每次按热水按钮后的 k 秒也会有热水，请你求出高桥自己最少按几次热水按钮可以让他在整个洗澡过程中的 t 秒内都有热水用。

思路

事实上，这是一道时间复杂度 O(n) 依次遍历就能解决的水题，我们维护变量 cur 来记录目前水最久能从0 秒流道什么时候，每次别人按按钮的时候就把 cur 更新往后推。
如果遇到第 i 次别人按按钮前没有热水，就直接把这个空档的时间除一下然后令答案加上这个数。

代码

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define long long int;
const int maxn=200010;
int n,t,k,ans=0;//题目里的条件以及高桥自己要按几次
int cur=0;//当前水最久能流多久
int a[maxn];

int main(){
    cin>>n>>k>>t;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    //排序一下别人按按钮的顺序确保遍历不出错
    for(int i=1;i<=n;i++){
        if(a[i]>=t) break;
        //如果这人按按钮已经是在题目要求的时间之后了，直接不管
        if(cur<a[i]){
        //如果目前能流的时间距离下一次别人按按钮有空档
            int gap=a[i]-cur;
            //求出这个空档
            int cnt=(gap+k-1)/k;
            //求出要按几次才能满足这个空档
            ans+=cnt;
            //答案加上这个次数
            cur+=cnt*k;
            //最远能流多久更新
        }
        cur=max(cur,a[i]+k);
        //如果别人帮助高桥按了，那么水流最久也要更新
    }
    if(cur<t){
    //如果最后一次别人按按钮之后仍不满足，就把还剩下多少到t的时间求出，一口气按完
        int gap=t-cur;
        int cnt=(gap+k-1)/k;
        ans+=cnt;
    }
    cout<<ans;
}