25 pts 求助
查看原帖
25 pts 求助
351679
shaun2000楼主2024/7/3 15:52
#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)
        {
            //printf("i=%d f=%d l=%d\n ",i,p[q.front()],p[i-1]);
            ans++;
        }

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

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