题解：P13916 [PO Final 2024] 瓦萨滑雪节 / Vasaloppet

· · 题解

大体思路：

查看本题的时空限制，我们可以发现本题空间格外大，这么大的空间，足以让我们开 10^9 次方大小的 bool 数组 z，z_i=1 表示第 i 秒开始的一秒之内有广告，反之没有。我们可以先算出从第 0 秒开始滑雪，错过的节目时间，接着将滑雪时间逐步向后移，直到没法移为止，取这之中错过节目时间的最小值就可以了。

对于每一次移动，滑雪时间会包含一个新的时间点，去掉一个旧的时间点，而我们只需要在前一个滑雪时间错过节目时间的基础上处理这两个时间点造成的影响即可，时间复杂度就不高了。如果加入的时间是广告，那么现在错过节目的时间就会减一；如果去掉的时间是广告，那么现在错过节目的时间就会加一。

代码：

#include<bits/stdc++.h>
using namespace std;
bool z[1000000005];
int main(){
    int n,t,s;
    scanf("%d%d%d",&n,&t,&s);
    int l,r;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&l,&r);
        for(int j=l;j<r;j++){   //记录广告时间。
            z[j]=1;
        }
    }
    int sum=0,ans=0;
    for(int i=0;i<s;i++){   //计算从 0 开始滑雪错过的节目时间。
        if(!z[i])sum++;
    }
    ans=sum;
    for(int i=1;i<=t-s;i++){  //后移滑雪时间，求答案。
        if(!z[i+s-1])sum++;
        if(!z[i-1]){sum--; }
        ans=min(ans,sum);
    }
    printf("%d",ans);
    return 0;
}