AdditionalFile4894.zip

P3572 [POI 2014] PTA-Little Bird

题目描述

有 $n$ 棵树排成一排，第 $i$ 棵树的高度是 $d_i$。

有 $q$ 只鸟要从第 $1$ 棵树到第 $n$ 棵树。

当第 $i$ 只鸟在第 $j$ 棵树时，它可以飞到第 $j+1, j+2, \cdots, j+k_i$ 棵树。

如果一只鸟飞到一颗高度大于等于当前树的树，那么它的劳累值会增加 $1$，否则不会。

由于这些鸟已经体力不支，所以它们想要最小化劳累值。

输入格式

第一行输入 $n$。

第二行 $n$ 个数，第 $i$ 个数表示 $d_i$。

第三行输入 $q$。

接下来 $q$ 行，每一行一个整数，第 $i$ 行的整数为 $k_i$。

输出格式

共 $q$ 行，每一行输出第 $i$ 只鸟的最小劳累值。

输入输出样例 #1

输入 #1

9
4 6 3 6 3 7 2 6 5
2
2
5

输出 #1

2
1

说明/提示

$1 \le n \le 10^6$，$1 \le d_i \le 10^9$，$1 \le q \le 25$，$1 \le k_i \le n - 1$。

#4894. 「POI2014 R2」小鸟 Little Bird

标签: 传统 | 时间限制: 10000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXI Olimpiada Informatyczna — II etap Ptaszek

在字节森林中，$n$ 棵树木排成一列。一只小鸟站在第一棵树的树梢，想飞到最后一棵树的顶端。它还年幼，体力有限，可能无法一口气飞完全程。若小鸟在第 $i$ 棵树的树梢，它一次飞行可到达第 $i+1, i+2, \ldots, i+k$ 棵树，之后必须停下休息。

向上飞对小鸟来说格外吃力：从较低或等高的树飞到更高或等高的树会让它疲惫不堪，而向下飞则轻松无忧。你需要为小鸟规划落脚的树木，让它尽可能少地感到疲惫。此外，小鸟有几位朋友也想从第一棵树飞到最后一棵树，它们的体力各不相同（即 $k$ 值不同）。请你也帮帮它们！

输入格式

输入第一行包含一个整数 $n$ $(2 \leq n \leq 1000000)$，表示字节森林的树木数量。

第二行包含 $n$ 个整数 $d_{1}, d_{2}, \ldots, d_{n}$ $(1 \leq d_{i} \leq 10^{9})$，$d_{i}$ 表示第 $i$ 棵树的高度。

第三行包含一个整数 $q$ $(1 \leq q \leq 25)$，表示需要考虑飞行的鸟儿数量。

接下来的 $q$ 行描述鸟儿，每行一个整数 $k_{i}$ $(1 \leq k_{i} \leq n-1)$，表示第 $i$ 只鸟儿的体力，即它一次飞行最多可跳过的树木数为 $k_{i}$。

输出格式

输出 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 只鸟儿最少需要从较低或等高树飞到更高或等高树的次数。

样例

输入

9
4 6 3 6 3 7 2 6 5
2
2
5

输出

2
1

第一只鸟儿可依次停在 $1, 3, 5, 7, 8, 9$ 号树，需在第 $3$ 到第 $5$ 棵树和第 $7$ 到第 $8$ 棵树向上飞，共疲惫 $2$ 次。

附加样例

1. $n=11, q=1, k_{1}=5$，所有树高相等，答案为 $2$（在第 $6$ 棵树中途休息即可）；
2. $n=100, q=2, k_{1}=5, k_{2}=6$，树高交替为 $1$ 和 $2$，两种鸟儿每 $5$ 棵树休息一次，各疲惫 $11$ 次；
3. $n=100, q=1, k_{1}=10$，树高为 $100, 99, \ldots, 1$，答案为 $0$；
4. $n=1000000, q=25, k_{i}=i$，$d_{1000}=d_{2000}=d_{3000}=\ldots=d_{1000000}=2$，其余 $d_{i}=1$。

数据范围与提示

对于 $70\%$ 的数据，$n \leq 100000$。
对于其中 $30\%$ 的数据，$n \leq 1000$。