壁画

题目 壁画

image-10822648

思路分析

每天只能画一幅壁画 且最边上的一面墙会被销毁（只能销毁没被画的）

然后第二天只能画在已经画过的旁边的墙上

所以最后的结果一定是连续的某段的总和

那么就可以想到用前缀和求

怎么控制l和r 因为前缀和要s[r]-s[l-1]

可以发现

5面墙无论怎么画 最后一定是连续的3个被画

4面墙无论怎么画 最后一定是连续的2个被画

3面一定是2 6面一定是3

其实就是 对于偶数面墙n 最后连续的区间len为n/2

对于奇数面墙n 最后连续的区间len长度为n/2+1

那么就锁定了一个窗口大小

答案就直接在l=1，r=len ；r≤n ；l++，r++里面咯

用一个max去更新答案 找到最大的 即可

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=5e6+10;
char a[N];
int s[N];
int T,n,cnt=0;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            s[i]=s[i-1]+(a[i]-'0');
        }

        int len;
        if(n%2==0)
            len=n/2;
        else
            len=n/2+1;

        int ans=0;
        for(int l=1,r=len;r<=n;l++,r++)
            ans=max(ans,s[r]-s[l-1]);
        cnt++;
        cout<<"Case #"<<cnt<<": "<<ans<<endl;
    }
    return 0;
}

同类题型

视频讲解

⬅️ 前缀和 🏠 00-刷题理模型 ➡️ 局部和