题解 | #最多数组数量#

一道前缀和的应用 最快得到一个区间的和就用前缀和，其中暴力两次循环可以得到符合题目性质的解的数量，但肯定会超时，这时就需要考虑能不能优化成n的规模解决问题，根据前缀和单调递增的性质可以发现随着遍历i的取值j一定只会往后增大这时只要当每一次循环时找到符合要求的j的位置，如果符合当前i的位置的性质要求答案就加上从j到n-1所有解的数量因为当前j符合要求随着j增加中间部分会越来越大而右边会越来越小所以就是j~n-1,虽然也是两次循环但j只要到n-1时便不会继续循环所以时间规模只是n,代码如下

#include <iostream>
using namespace std;
long long sum[200010];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>p;
        sum[i]=sum[i-1]+p;
    }
    long long cnt=0;
    int j=2;
    for(int i=1;i<=n-2;i++)
    {
        while(j<n-1&&!((sum[j]-sum[i])>sum[i]&&(sum[j]-sum[i])>(sum[n]-sum[j])))
            j++;
        if((sum[j]-sum[i])>sum[i]&&(sum[j]-sum[i])>(sum[n]-sum[j]))
            cnt+=n-j;
    }
    cout<<cnt;
    return 0;
}