人类基因组

问题描述

输入格式

输出格式

样例输入

样例输出

数据范围

题解

把初始串复制一遍，接在后面，然后求前缀和sum

则Ak,Ak+1,……,An-1,A0,A1……,Ak-1即为Ak,Ak+1,……,An-1,An,An+1……,An+k-1

任意的前i项和为sum[i]-sum[k-1]

满足对于任意的前 和都满足不小于0,即从k到n+k-1这段区间的任意sum[i]>=sum[k-1],只要最小的sum[i]>=sum[k-1]就行了。

单调队列从后往前维护最小值即可。

#include <cstdio>
int n,a[1000005],sum[2000005];
int q[5000005][2],h,t,ans;
int main()
{
    int i,j;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
      scanf("%d",&a[i]),
      sum[i]=sum[i-1]+a[i],
      sum[i+n]=a[i];
    int n2=n<<1;
    for (i=n+1;i<=n2;i++) 
      sum[i]+=sum[i-1];
    q[++t][0]=sum[n2-1]; q[t][1]=n2-1; h=1;
    for (i=n2-2;i>=n;i--)
    {
        while (sum[i]<q[t][0] && t>=h) t--;
        q[++t][0]=sum[i];  q[t][1]=i;
    }
    for (i=n;i>=1;i--)
    {
        if (q[h][0]>=sum[i-1]) ans++;
        while (q[h][1]-n+1>i && h<t) h++;
        while (sum[i-1]<q[t][0] && t>=h) t--;
        q[++t][0]=sum[i-1];  q[t][1]=i-1;
    }
    printf("%d",ans);
    return 0;
}