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

· · 题解

单调队列找规律什么的方法都没想到，用了种比较奇怪的方法水过了这道题。

对于每一个数a[k]，先预处理出从k~n是否能走和从1~k是否能走。

过程：

1.判断1~k是否能走，即判断Σi=k~n a[i]和min{a[1],a[1]+a[2],a[1]+a[2]+a[3],…,Σi=1~k a[i]}的相反数之间的大小关系。

2.判断k~n是否能走，即判断Σi=k~n a[i]过程中是否出现过负数。

3.对于任一满足1.2.两个条件的元素，对答案贡献为1。

    //判断1~k是否能走
    //求min{a[1],a[1]+a[2],a[1]+a[2]+a[3],…,Σi=1~k a[i]}
    for (int i=1;i<=n;++i)
    {
        sum-=a[i];
        f[i]=max(sum,f[i-1]);
    }
    //前缀和计算Σi=k~n a[i]
    //判断
    //判断k~n是否能走
    //sum表示如需将i作为k点，需要另外支付的内容
    for (int i=n;i>=1;--i)
    {
        sum=max(sum-a[i],0-a[i]);
        if (sum<=0) g[i]=1;
    }

O(n)求1.2.：

完整代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
int a[1000001],f[1000001];
bool g[1000001];
int main()
{
    int n,sum=0;
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        sum-=a[i];
        f[i]=max(sum,f[i-1]);
    }
    sum=0;
    for (int i=n;i>=1;--i)
    {
        sum=max(sum-a[i],0-a[i]);
        if (sum<=0) g[i]=1;
    }
    for (int i=1;i<=n;++i) a[i]+=a[i-1];
    int ans=0;
    for (int i=1;i<=n;++i)
        if (g[i]&a[n]-a[i-1]>=f[i-1]) ans++;
    printf("%d",ans);
}