Skip to content

S2OJ - 1470. 饥饿的小鸟

题解717 字
# 贪心 # S2OJ
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

题面

题目描述

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

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

输入格式

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

输出格式

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

输入输出样例

样例输入 #1

10 5
0 0 1 0 2 0 0 1 0

样例输出 #1

3

样例解释 #1

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

样例输入 #2

10 3
1 1 1 1 2 1 1 1 1

样例输出 #2

3

样例解释 #2

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

数据范围与约定

对于 20%20\% 的数据，L=N−1L = N - 1；
对于 50%50\% 的数据，1≤L<N≤51 \leq L < N \leq 5，0≤Ai≤30 \leq A_i \leq 3；
对于 80%80\% 的数据，1≤L<N≤1001 \leq L < N \leq 100，0≤Ai≤100 \leq A_i \leq 10；
对于 100%100\% 的数据，1≤L<N≤1051 \leq L < N \leq 10^5，0≤Ai≤1040 \leq A_i \leq 10^4。

思路

贪心。

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

代码

#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;
}