52 lines
956 B
Markdown
52 lines
956 B
Markdown
# 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$。 |