好消息 坏消息 P2629

单调队列 最小前缀和 T3 https://vjudge.csgrandeur.cn/problem/%E6%B4%9B%E8%B0%B7-P2629

题目描述

Uim 在公司里面当秘书，现在有 $n$ 条消息要告知老板。每条消息有一个好坏度，这会影响老板的心情。告知完一条消息后，老板的心情等于老板之前的心情加上这条消息的好坏度。最开始老板的心情是 $0$，一旦老板心情到了 $0$ 以下就会勃然大怒，炒了 Uim 的鱿鱼。

Uim 为了不被炒，提前知道了这些消息（已经按时间的发生顺序进行了排列）的好坏度，希望知道如何才能不让老板发怒。

Uim 必须按照事件的发生顺序逐条将消息告知给老板。不过 Uim 可以使用一种叫 “倒叙” 的手法，例如有 $n$ 条消息，Uim 可以按 $k,k+1,k+2,\dots ,n,1,2,\dots ,k-1$（事件编号）这种顺序通报。

他希望知道，有多少个 $k$，可以使从 $k$ 号事件开始通报到 $n$ 号事件然后再从 $1$ 号事件通报到 $k-1$ 号事件可以让老板不发怒。

输入格式

第一行一个整数 $n$（$1\le n\le 10^6$），表示有 $n$ 个消息。

第二行 $n$ 个整数，按时间顺序给出第 $i$ 条消息的好坏度 $A_i$（$-10^3\le A_i\le 10^3$）。

输出格式

一行一个整数，表示可行的方案个数。

样例 #1

样例输入 #1

4
-3 5 1 2

样例输出 #1

2

提示

【样例解释】

通报事件的可行顺序（用编号表示）为 $2\to 3\to 4\to 1$ 或 $3\to 4\to 1\to 2$（分别对应 $k=2$ 和 $k=3$）

通报事件的可行顺序（用好坏度表示）为 $5\to 1\to 2\to (-3)$ 或 $1\to 2\to (-3)\to 5$

【数据范围】

对于 $25\%$ 的数据，$n\le 10^3$；
对于 $75\%$ 的数据，$n\le 10^4$；
对于 $100\%$ 的数据，$1\le n\le 10^6$。

思路

TSP旅行商问题的简化版， 先断环成链， 把数组复制一份，对应样例 -3 5 1 2 -3 5 1 2。

题目要求是在 $[k,k+n]$ （循环数组中）确保不会出现一个最小前缀和其值小于0, 即 $s_j-s_k<0,j=k+1,k+2,\dots ,k+n$。因此我们可以用单调队列维护区间内最小的 $s_j$, 如果最小的都是非负数, 那么整个区间就成立。

接下来就是循环枚举 $i$ 即 $k+n$, 同时维护 $[i-n,i]$ 区间内的最小值作为 $s_j$, 如果存在 $s_j-s_{i-n-1}$（多减一个1才是区间 $[i-n,j]$ 的和）, 则标记 $re{s}_{i-n}$ 为 FALSE, 表示该 $k$ 值不成立。 最后再统计一下 $re{s}_i$ 为 TRUE 的数量, 或者直接不用 $res$ 数组, 当成立时累加答案也可以。

因为我们是直接拷贝了一份数组， 故当 $i>n$ 时候才去更新对应的 $s_i$。

为什么这里跟旅行商问题的计算不太一样呢？ 同样都是求最小前缀和, 旅行商是 $s_i-s_j$ 单调队列维护 $s_j$ 的最大值, 而这里是 $s_j-s_{i-n-1}$ , 维护的是 $s_j$ 的最小值。可以发现, 前者是维护减数, 后者是维护被减数。

而并不能直接套用旅行商问题的方法, 因为这里是顺时针计算, 而旅行商中 $s_i-s_j$ 维护最大的 $s_j$ 时是逆时针计算。

旅行商的顺时针计算可以带入到这道题, 逆序枚举 $k$, 维护 $j=k+n$ 的最小值 $s_j$ , 同样是 $s_{k-1}-s_j$。不过更容易理解些。注意需要先插入队尾再更新答案, 且队列初始时不加入0, 因为求得是最小值。

代码

#include <bits/stdc++.h>
using namespace std;
 
const int N = 3e6;
int st[N], s[N], q[N];
 
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i + n] = s[i];
    }
 
    for (int i = 1; i <= 2 * n; i++)
        s[i] += s[i - 1];
 
    int hh = 0, tt = -1;
    for (int i = n * 2; i; i--)
    {
        if (hh <= tt && q[hh] >= i + n)
            hh++;
        while (hh <= tt && s[q[tt]] >= s[i])
            tt--;
        q[++tt] = i;
        if (i <= n)
            if (s[q[hh]] - s[i - 1] >= 0)
                st[i] = true;
    }
 
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        if (st[i])
            res++;
    }
 
    cout << res << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}