洛谷-P2629 好消息，坏消息题解

题目链接：https://www.luogu.com.cn/problem/P2629

题目分析

Uim 需要向老板报告 n 条消息，每条消息有好坏度 Ai。老板初始心情为 0，报告每条消息后心情增加 Ai。若心情低于 0，Uim 被解雇。Uim 可以选择一个起始点 k（1≤k≤n），先报告第 k 到第 n 条消息，再报告第 1 到第 k−1 条消息。求有多少个 k 使得整个报告过程中心情始终 ≥0。

通过观察可以发现以下几点

总和约束：所有消息的总和 S 必须 ≥0。若 S<0，报告完所有消息后心情为负，直接无解。
报告过程拆分：

设s为分割点：

右半部分：消息 [s,n−1]，心情从 0 开始。要求该部分所有前缀和 ≥0。
左半部分：消息 [0,s−1]，心情从右半部分总和 R 开始。要求 R+左半部分任意前缀和≥0。

3.前缀和优化：

定义前缀和数组 presum[i]：用于快速求左右部分的和。

算法设计

前缀和与总和：计算前缀和数组 presum 和总和 S。若 S<0，直接输出 0。
检查 k=1（原顺序）：若所有前缀和 presum[i]≥0（0≤i<n），则 k=1 可行，初始化 ans=1；否则 ans=0。
单调队列维护极值：右半部分最小值：用单调递增队列 rminQ 存储 presum 索引，队首是 [i+1,n−1] 的最小值。左半部分最小值：用单调递增队列 lminQ 动态维护 [0,i] 的最小值。
枚举分割点：遍历 i 从 0 到 n−2：更新 lminQ（加入 i）和 rminQ（移除 ≤i 的索引）。计算左半部分和 L=presum[i]，右半部分和 R=S−L。检查两个条件：右半部分有效：presum[rminQ.front()]−L≥0（右半部分所有前缀和 ≥0）。左半部分有效：R+presum[lminQ.front()]≥0（左半部分所有心情 ≥0）。若均满足，ans 增加 1。

复杂度分析

时间复杂度：O(n)。每个元素最多入队和出队一次。
空间复杂度：O(n)。存储前缀和与队列。

代码解析

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> presum(1000001); // 前缀和数组
    vector<int> lminQ(1000001), rminQ(1000001); // 单调队列
    int ll = 0, lr = 0, rl = 0, rr = 0; // 队列指针
    int ans = 1, sum = 0; // ans 初始化为 k=1 的情况

    // 输入并计算前缀和，初始化右队列
    for (int i = 0; i < n; i++) {
        cin >> presum[i];
        sum += presum[i];
        // 检查 k=1：若当前前缀和<0，则 k=1 不可行
        if (sum < 0) ans = 0;
        // 维护右半部分的单调递增队列（整个数组）
        while (rl < rr && presum[rminQ[rr - 1]] >= presum[i])
            rr--;
        rminQ[rr++] = i;
    }

    // 总和<0，无解
    if (sum < 0) {
        cout << 0;
        return 0;
    }

    // 枚举分割点 i（左半部分 [0,i]）
    int lsum = 0, rsum;
    for (int i = 0; i < n - 1; i++) {
        // 维护左半部分 [0,i] 的单调递增队列
        while (ll < lr && presum[lminQ[lr - 1]] >= presum[i])
            lr--;
        lminQ[lr++] = i;

        // 移除右队列中索引 <= i 的元素（右半部分从 i+1 开始）
        if (rl < rr && i == rminQ[rl])
            rl++;

        lsum = presum[i]; // 左半部分和
        rsum = sum - lsum; // 右半部分和

        // 检查两个条件
        if (presum[rminQ[rl]] - lsum >= 0 && rsum + presum[lminQ[ll]] >= 0)
            ans++;
    }

    cout << ans;
    return 0;
}

正确性说明

总和检查：S<0 时直接退出，确保最终心情 ≥0。
k=1 处理：在输入时检查所有前缀和，若全 ≥0 则 ans=1，否则 0。
单调队列：rminQ 初始化为整个数组的单调递增队列，循环中弹出 ≤i 的索引，保证队首是 [i+1,n−1] 的最小值。lminQ 动态维护 [0,i] 的最小值。
条件验证：presum[rmin]−L≥0 确保右半部分所有前缀和 ≥0。R+presum[lmin]≥0 确保左半部分所有心情 ≥0。