S2OJ - 1470. 饥饿的小鸟

#题面

#题目描述

一群饥饿的小鸟，要到河对岸吃东西。河的宽度为 $N$ 米，小鸟每飞行 $L$ 米就必须在一片荷叶上休息一下，才能够继续飞行。当然，小鸟们也可以选择没飞够 $L$ 米就先休息一下，但不能一次飞超过 $L$ 米。距离小鸟们出发的河岸一侧距离为 $i$ 的荷叶共有 $A_i$ 片，每片荷叶在有小鸟停于上方休息后，就会沉入水底，不能够再供其他小鸟休息。

现在想要知道，至多有多少只小鸟能够抵达对岸。

#输入格式

第一行输入两个整数 $N, L$，含义见题面描述。 接下来一行 $N-1$ 个整数 $A_i$，表示距离河的出发一侧距离为 $i$ 的荷叶的片数。

#输出格式

输出一行一个整数，表示至多能够抵达前线的小鸟数量。

#输入输出样例

样例输入 #1

10 5
0 0 1 0 2 0 0 1 0

样例输出 #1

3

样例解释 #1

三只小鸟可以分别走 $0 → 5 → 10$；$0 → 5 → 10$；$0 → 3 → 8 → 10$。

样例输入 #2

10 3
1 1 1 1 2 1 1 1 1

样例输出 #2

3

样例解释 #2

三只小鸟可以分别走 $0 → 1 → 4 → 7 → 10$；$0 → 2 → 5 → 8 → 10$；$0 → 3 → 6 → 9 → 10$。

#数据范围与约定

对于 $20\%$ 的数据，$L = N - 1$；
对于 $50\%$ 的数据，$1 \leq L < N \leq 5$，$0 \leq A_i \leq 3$；
对于 $80\%$ 的数据，$1 \leq L < N \leq 100$，$0 \leq A_i \leq 10$；
对于 $100\%$ 的数据，$1 \leq L < N \leq 10^5$，$0 \leq A_i \leq 10^4$。

#思路

贪心。

尽可能使用当前点能达到的最远距离的承载容量，然后转移即可。

#代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
#include <cstring>
#include <limits>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int n, l, s, a[N], b[N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> l;

    for (int i = 1; i < n; i++) {
        cin >> a[i];

        s += a[i];
    }

    a[n] = b[0] = s;
    for (int i = 0; i < n; i++) {
        for (int j = std::min(i + l, n); j > i; j--) {
            if (b[j] < a[j]) {
                if (b[j] + b[i] <= a[j]) {
                    b[j] += b[i];
                    b[i] = 0;
                    break;
                } else {
                    b[i] -= a[j] - b[j];
                    b[j] = a[j];
                }
            }
        }
    }

    cout << b[n] << endl;

    return 0;
}