P2629 好消息，坏消息 题解

user100566 · 2024-12-04 18:45:33 · 题解

详细地讲一下用前缀和思想 O(n) 求解本题的方法，而且只需要额外定义一个布尔数组，时间和内存都是目前最优的：总 123ms，最大 15ms, 4.36MB 的最优解。

题目分析

给定一个长度为 n\le10^6 的整数数组 A(-1000\le A_i\le1000)，找出有多少个 k 满足：

为了方便处理 A_n 到 A_1 的突变，我们分类讨论。
考虑某个不合法的 k，如果在 A_1 之前出现负的前缀和，则称这个 k 是后缀不合法的，反之则为后缀合法的，如果在 A_n 之后出现负的前缀和，则称这个 k 是前缀不合法的，反之则为前缀合法的。

显然，一个 k 合法当且仅当它既后缀合法，也前缀合法。

后缀合法的判定

如果某个 k 是后缀合法的，则前缀和 A_k+A_{k+1}+A_{k+2}+\dots+A_j(k\le j\le n) 恒为非负值。
用 B_i 表示后缀和 A_i+A_{i+1}+A_{i+2}+\dots+A_n(1\le i\le n), B_{n+1}=0，则上式可表示为：

由上式恒成立，可得出以下等价式：

维护后缀和 B 后，从大到小枚举 k，根据上式判断是否后缀合法，然后更新 \min\{B_{j}\} 的值即可。

事实上并不需要真的维护后缀和数组 B，从大到小枚举 k 时，可以直接根据前一个 B_{k+1} 递推得出 B_k=B_{k+1}+A_k，然后用一个布尔数组表示是否后缀合法，无需其它额外空间。

前缀合法的判定

如果某个 k 是前缀合法的，则前缀和 A_k+A_{k+1}+A_{k+2}+\dots+A_n+A_1+A_2+\dots+A_j(1\le j\le k-1) 恒为非负值。
再定义 C_i 表示前缀和 A_1+A_2+A_3+\dots+A_i(0\le i\le n), C_0=0，则上式可表示为：

由上式恒成立，可得出以下等价式：

维护 B 和 C 后，从小到大枚举 k，根据上式判断是否前缀合法，然后更新 \max\{C_{j}\} 的值即可。

但是，前面判定后缀合法时已经进行了优化，没有真正的 B 数组，如何解决这个问题呢？
还是考虑递推，如果已知 B_k，那么可以知道 B_{k+1}=B_k-A_k，因此只需要知道 B_1，而这前面判定后缀合法时最后得到的后缀和，因此只需要在前一步保留这个值即可。

同样的，也不需要真的维护数组 C，还是可以递推得出 C_{k+1}=C_k+A_k。

其它优化

可以使用 std::bitset 压缩后缀合法布尔数组的大小，同时不需要维护前缀合法布尔数组：在判定前缀合法时，如果 k 已经是后缀合法的，且通过公式得知 k 也是前缀合法的，则 k 是一个合法的取值，答案加 1。

代码

云剪贴板存档

#include <cstdio>
#include <algorithm>
#include <bitset>
using namespace std;
// 快读
#ifdef ONLINE_JUDGE
#define getchar() getchar_unlocked()
#endif
inline int read(){
    int c = getchar();
    while(c<45||c>57) c = getchar();
    // '-' 的 ASCII 值为 45 
    if(c==45){
        int x = 0;
        c = getchar();
        while(48<=c&&c<=57){
            x = (x<<3)+(x<<1)+(c^48);
            c = getchar();
        }
        return -x;
    }else{
        int x = 0;
        while(48<=c&&c<=57){
            x = (x<<3)+(x<<1)+(c^48);
            c = getchar();
        }
        return x;
    }
}

// 下标全部从 0 开始 
int n, a[1000000];
// 注意 bitset 赋初值 false
bitset<1000000> b(false);

int main(){
    n = read();
    for(int i=0; i<n; ++i) a[i] = read();
    // 后缀和，最大后缀和 
    int suf = 0, maxsuf = 0;
    for(int i=n-1; ~i; --i){
        suf += a[i];
        // 最小区间和 = suf-maxsuf>=0 
        if(suf>=maxsuf) b[i] = true;
        maxsuf = max(maxsuf, suf);
    }
    int ans = 0;
    // 前缀和，最小前缀和 
    int pre = 0, minpre = 0;
    for(int i=0; i<n; ++i){
        // 最小区间和 = suf+minpre>=0 
        if(b[i] && suf>=-minpre) ++ans;
        pre += a[i];
        minpre = min(minpre, pre);
        suf -= a[i];
    }
    printf("%d", ans);
    return 0;
}