检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。
题面
题目描述
一群饥饿的小鸟,要到河对岸吃东西。河的宽度为 米,小鸟每飞行 米就必须在一片荷叶上休息一下,才能够继续飞行。当然,小鸟们也可以选择没飞够 米就先休息一下,但不能一次飞超过 米。距离小鸟们出发的河岸一侧距离为 的荷叶共有 片,每片荷叶在有小鸟停于上方休息后,就会沉入水底,不能够再供其他小鸟休息。
现在想要知道,至多有多少只小鸟能够抵达对岸。
输入格式
第一行输入两个整数 ,含义见题面描述。 接下来一行 个整数 ,表示距离河的出发一侧距离为 的荷叶的片数。
输出格式
输出一行一个整数,表示至多能够抵达前线的小鸟数量。
输入输出样例
样例输入 #1
10 5
0 0 1 0 2 0 0 1 0
样例输出 #1
3
样例解释 #1
三只小鸟可以分别走 ;;。
样例输入 #2
10 3
1 1 1 1 2 1 1 1 1
样例输出 #2
3
样例解释 #2
三只小鸟可以分别走 ;;。
数据范围与约定
对于 的数据,;
对于 的数据,,;
对于 的数据,,;
对于 的数据,,。
思路
贪心。
尽可能使用当前点能达到的最远距离的承载容量,然后转移即可。
代码
#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;
}