题解 P2629 【好消息，坏消息】

· · 题解

最近的训练内容是单调队列，于是就找来一些题目练练手。

对于这道题，显然k有n种可能的情况，我们只要对每个k判断是否合法即可。但如果暴力枚举每一个k，时间复杂度是 的，需要考虑优化。

在考虑优化前，我们先介入一种思想——断环为链，这样可以方便处理对于每一个k的情况。说通俗点就是在n后面再接上1--(n-1)的值，所以数组要开双倍长度。

以样例为例：-3 5 1 2，我们将其断环为链后可以得到这样的一组数据：-3 5 1 2 -3 5 1，并设其下标为1--7。当k=1时，需要判断的就是下标1--4；当k=2时，就是下标2--5；当k=3时，就是下标3--6；当k=4时，就是下标4--7（显然k不会等于5）。

断环为链后，题目要求就变为了：对于每一个合法的k，都要满足k--(n+k-1)中，到任意一点的和都是非负的。熟悉前缀和的人应该知道，如果用s[i]表示1--i的所有数的和，那么s[j]-s[i-1]就是i--j所有数的和。所以用前缀和预处理后，s[i]-s[k-1]就是k--i(k<=i<=n+k-1)的和了，我们只要判断这个和是否为负即可。

既然这么说，那么是否要判断k--n+k-1中每一个数的和呢？当然不是，因为其中如果只要有一点的和是负的，那么这个k就是不合法的了，所以我们只需要判断一次——判断最小的si减去s[k-1]是否为负。

那么这题的思路就很明确了，先对输入数据断环为链，然后在链上进行前缀和的预处理，最后，对于每一个k+n-1，我们用单调队列维护k--k+n-1的最小值，并将其减去s[k-1]判断是否合法。

代码如下：

#include<cstdio>
#include<iostream>
using namespace std;
int n,head=1,tail,ans;
long long a[2000001],s[2000001],q[2000001];
int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i+=1)
        scanf("%lld",&a[i]);
    for(register int i=1;i<=n-1;i+=1)
        a[i+n]=a[i];
    for(register int i=1;i<=2*n-1;i+=1)
        s[i]=s[i-1]+a[i];
    for(register int i=1;i<=2*n-1;i+=1)
    {
        while(head<=tail&&max(i-n+1,1)>q[head])head++;
        while(head<=tail&&s[i]<=s[q[tail]])tail--;
        q[++tail]=i;
        if(i-n+1>0&&s[q[head]]-s[i-n]>=0)ans++;
    }
    printf("%d\n",ans);
    return 0;
}