CF961B Lecture Sleep 题解

· · 题解

题目传送门

考虑到如果用本题的题目翻译解释此题会比较难理解，因此提供一下自己的翻译。

题意

你的朋友 Mishka 和你一起参加了一个微积分课程，这个课程总共 n 分钟，第 i 分钟会讲授 a_i 条定理。

Mishka 对这个课程非常有兴趣，但他无法保证在课上的每分钟都保持清醒状态。现在给定你一个序列 t，用来描述 Mishka 每分钟的状态。如果 Mishka 在第 i 分钟处于昏睡状态，t_i 等于 0，处于清醒状态 t_i 等于 1。如果 Mishka 第 i 分钟处于清醒状态，他会记下第 i 分钟讲授的 a_i 条定理，否则他什么都不会记下。

你知道一条秘籍可以使 Mishka 保持清醒 k 分钟，但你只能使用 1 次，在 1 至 n-k+1 区间内的每分钟开始时都可以使用。

你的任务是使用秘籍使 Mishka 记下最多的定理。

思路

最笨的方法就是对于 1 至 n-k+1，每一分钟试一下去使用秘籍，最后找出最优方案，复杂度 O(nk)，很显然不能过，因此这道题目可以考虑用双指针法来解决。

我们定义两个指针 x 和 y，代表左指针和右指针，而这两个指针中间的区域就是我们使用秘籍的地方。

使用秘籍的最优方案应该是在 Mishka 错过最多定理的 k 分钟内使用秘籍，这样就能使 Mishka 听到尽可能多的定理。

AC Code

#include<iostream>
using namespace std;
int a[100005];
int t[100005];

int main(){
    int n,k,x,y,cnt=0,maxx=0,maxt,maxw;//cnt是使用秘籍的区间ti=0时ai的和
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>t[i];
    for(int i=1;i<=k;i++){
        if(t[i]==0) cnt+=a[i];//预处理
    } 
    x=1;
    y=k;
    while(x<=n-k+1){
        if(cnt>maxx){//打擂台求最优方案
            maxx=cnt;
            maxt=x;//记录这个使用秘籍的区间
            maxw=y;
        }
        if(t[x]==0) cnt-=a[x];//删掉左端点 Mishka在睡觉 错过了这些定理
        x++;
        y++;
        if(t[y]==0) cnt+=a[y];//新加入右端点 Mishka不再睡觉 多记了一些定理
    }
    for(int i=1;i<=n;i++){
        if(i>=maxt && i<=maxw && t[i]==0) continue;//区间内ti=0的情况已经算过了
        maxx+=a[i]*t[i];//没算的再加
    }
    cout<<maxx;
    return 0;
}