ABC443C题解 Chokutter Addiction 带本土化翻译-编程学习交流讨论版论坛-综合讨论-ZDZL
AI 文章摘要
该题解针对ABC443C题,核心思路是模拟。高桥君在0到T时间内观看洛谷网校,青木君在特定时刻检查,高桥君每次关闭后等待100秒再重开。解法通过变量s记录当前观看开始时间,遍历检查时间点,若检查时间晚于s,则累加从s到该时间点的观看时长,并将s更新为检查时间+100秒。最后加上从s到T的剩余时间。时间复杂度O(n)。

ABC443C题解 Chokutter Addiction 带本土化翻译

### 题目大意
高桥君在 $0$ 到 $T$ 时间内在工作,他在工作时想观看洛谷网校。

高桥君非常热爱洛谷网校课程,所以他从第 $0$ 秒就在看。

但是青木君会来检查高桥君是否在摸鱼,已知青木君会在 $A_i$ 时间检查,高桥君会在检查时立刻关掉洛谷网校课程,每次关掉网校课程后会等待 $100$ 秒重开。

### 思路

主要考模拟。

通过一个当前观看网校时间 $s$ 来模拟过程。遍历青木君经过的时间点,每当遇到青木君在观看期间经过(即 `a[i] >= s`),就将从 $s$ 到该时间点的观看时间累加到答案中,然后将 $s$ 更新为经过时间加 $100$ 秒表示下次看的时间。

最后补算在最后一次检查以后的时间。

### Code

“`

#include<bits/stdc++.h>
using namespace std;
long long a[300010];

int main(){

    long long n,t;
    cin>>n>>t;
    for(int i=1;i<=n;i++)cin>>a[i];

    long long s=0,ans=0;
    for(int i=1;i<=n;i++){
           if(a[i]>=s){
                 if(min(a[i],t)>s)ans+=min(a[i],t)-s;
                 s=a[i]+100;
            }
    }
    if(t>s)ans+=t-s;

    cout<<ans<<endl;
}

“`

显然复杂度 $\mathcal{O(n)}$,可以通过。

![](https://cdn.luogu.com.cn/upload/image_hosting/a8s32gki.png)