25分求助
查看原帖
25分求助
351679
shaun2000楼主2024/7/3 15:25
#include<bits/stdc++.h>

using namespace std;
int a[2000005],p[2000005];
deque <int> q;
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i+n]=a[i];

    }
    for(int i=1;i<=2*n-1;i++)
        p[i]=p[i-1]+a[i];

    for(int i=1;i<n;i++)
    {
        while(!q.empty() && a[q.back()]>=a[i]) q.pop_back();
            q.push_back(i);
    }
    for(int i=1;i<n;i++)
    {
        while(!q.empty() && a[q.back()]>=a[i+n-1]) q.pop_back();
        q.push_back(i+n-1);
        while(!q.empty() && q.front()<i) q.pop_front();
        if(p[q.front()]-p[i-1]>=0)
        {
            ans++;
        }

    }
    cout<<ans<<"\n";

    return 0;
}
2024/7/3 15:25
加载中...