题目描述
https://codeforces.com/problemset/problem/893/D
Solution
注意到我们只需要在 $a_i=0$ 的天放钱即可
首先我们考虑将无解的情况判掉，即每次在 $a_i=0$ 的天中 $sum<0$ 我们就加到 $0$，否则就不加
如果这样还是超过 $d$，则一定无解
然后我们考虑这样一个贪心，每次都加到能加的最大值，证明并不会
至于如何得到最大值，在保证有解的情况下，我们直接加到 $d$，如果因为某个 $a_i>0$ 使得钱的总数大于 $d$，我们令其为 $d$ 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <iostream>
#include <cstdio>
#define maxn 100010
using namespace std;
int n, d, a[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> d; int s1 = 0, s2 = 0, ans = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (!a[i]) {
s1 = max(s1, 0);
if (s2 < 0) s2 = d, ++ans;
}
else {
s1 += a[i];
if (s1 > d) return cout << "-1\n", 0;
s2 = min(s2 + a[i], d);
}
} cout << ans << "\n";
return 0;
}
|