Solution.md

P2629

Link

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

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

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

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

输入格式

第一行一个整数 n, 表示有 n 个消息, 1 <= n <= 10的6次方

第二行 n 个整数，按时间顺序给出第 i 条消息的好坏度ai，-1000 <= ai <= 1000

输出格式

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

样例

in

4
-3 5 1 2

out

2

思路

从0开始计数，最后一个是第 n - 1 个

• 用f[i]表示以下数中最小的数:

  a[i]
  a[i] + a[i+1]
  a[i] + a[i+1] + a[i+2]
  ...
  a[i] + a[i+1] + a[i+2] + ... + a[n-1]

f[i]可以理解为从第i个开始汇报，一直到第 n - 1 个，这个过程中老板心情的最差值

• g[i]表示以下数中最小的数:

  a[0]
  a[0] + a[1]
  ...
  a[0] + a[1] + ... + a[i]

从第i个汇报到第 n - 1 个之后，再从第0个开始汇报到第 i - 1 个，
在汇报第0个到第 i - 1 个的过程中，老板最差心情 = g[i - 1]加上第i个到第 n - 1 个的好坏度之和

显然一个合法的k需要 f[k] >= 0 且 g[k-1] + (a[k] + a[k+1] + ... + a[n-1]) >= 0

f, g 可以在O(n)时间内算出，再判断每个i是否合法，整体时间复杂度O(n)

Code

#include <stdio.h>
#include <stdlib.h>
#define N 1000006
int a[N], sum[N], f[N], g[N];
static inline int min(int a, int b) { return a < b ? a : b; }

int main() {
    int n, i, ans = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        sum[i] = a[i] + (i ? sum[i - 1] : 0);
    }
    f[n - 1] = a[n - 1];
    for (i = n - 2; i >= 0; i--)
        f[i] = min(a[i], a[i] + f[i + 1]);
    g[0] = a[0];
    for (i = 1; i < n; i++)
        g[i] = min(g[i - 1], sum[i]);
    for (i = 0; i < n; i++)
        if (f[i] >= 0 && ( i == 0 || sum[n - 1] - sum[i - 1] + g[i - 1] >= 0)) ans++;
    printf("%d", ans);
    exit(0);
}