CF1057B 题解

· · 题解

CF1057B 题解

sjh：喵喵小课堂开课啦！我是蒟蒻 sjh，今天我们来学习 CF1057B 的解法！

喵喵们：好耶！

sjh：好的，fzj 你说一下思路。

fzj：这题十分的简单，我认为需要暴力枚举。

sjh：说的好，但是直接枚举的复杂度是 O(n^3)，所以怎么办呢？

lxx：前缀和！

sjh：很有道理，次掉。所以只需要双重循环枚举区间和，如果满足条件判断就可以啦！来，zzy 你把代码写出来。

zzy:（顺手加上了注释，我哭死）

#include<iostream>
using namespace std;
int n,a[5005],f[5005],ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        f[i]=f[i-1]+a[i];//前缀和
    }
    for(int i=1;i<=n;++i){
        for(int j=i;j<=n;++j){//枚举判断，注意i与j相等时也算区间
            if(f[j]-f[i-1]>(j-i+1)*100){//如果区间和大于长度*100，注意题目中的“超过”是大于不是大于等于！
                ans=max(ans,j-i+1);//取ans的max值
            }
        }
    }
    cout<<ans;
    return 0;
}

好了，下课。