题解：CF2224A Zhily and Array Operating

发表于 更新于 分类于 ， ， 本文字数： 226 阅读时长 ≈ 1 分钟
CF2224A Zhily and Array Operating 的题解

分析

显然我们的目标要使每个数尽可能的大，原因：

  • 尽可能大才能使这个数尽可能使整数。
  • 若这个数是正数，则可以前一个数做贡献，越大前一个数是正数的可能性越大。

而一个数变大需要其后一个数是正数，且越大越好。因此，考虑从后往前扫，若这个数加上后一个数可以更大，那么就加上后一个数。若加完后是正数，维护答案。

赛时吃了一发罚时，因为直接从 $N$ 到 1 扫，没有处理 a[N+1].

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
long long a[200005];
int main() {
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        a[n + 1] = 0;
        int ans = 0;
        for (int i = n; i >= 1; i--) {
            a[i] = max(a[i], a[i] + a[i + 1]);
            if (a[i] > 0) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}