CF1006C题解

Mr_Dolphin · 2021-07-26 14:16:57 · 题解

双向前缀和

看到dalao们用标记，瑟瑟发抖。萌新这里用前缀和数组+for循环代替了。（个人认为较容易理解）

前置知识

定义一个数组，第 i 项代表前 i 个数的和，那么这个数组就是原数组的前缀和数组。前缀和可用于求原数组任意一个区间的和，但本题只要用到定义即可。

方法

定义两个数组，一个是前缀和，另一个是反向的前缀和。因为本题要求前 i 与后 j 项相等。所以只用枚举 i 和 j ，再利用这两个数组求和即可。 对于每个 i ,注意 j 枚举是跳出循环的条件以避免TLE

代码实现

#include<iostream>
using namespace std;
int n,d[200001],a[200001],b[200001],ans;
int main()
{   
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>d[i];
        a[i]=a[i-1]+d[i];//前缀和
    }
    for(int i=n;i>0;i--)
    {
        b[i]=b[i+1]+d[i];//反向前缀和
    }
    for(int i=0;i<n+1;i++)//注意可以为零
    {
        for(int j=n+1;j>=i;j--)//j与i可相等
        {
            if(b[j]==a[i])//符合条件，更新答案
            {
                ans=max(ans,a[i]);
            }
            else
            {
                if(b[j]>a[i])//b[j]只会越来越大，所以不再相等，跳出循环
                {
                    continue;
                }
            }
        }
    }
    cout<<ans;
    return 0;//完结撒花
}

有什么错误，请dalao轻喷。

QAQ第一篇题解，求过QAQ