增量算法题目合集#

Problem Statement#

有 N 个脚手架排成一排，编号为 1 到 N 。第 i 个脚手架的高度为 H_i 。

高桥将进行如下游戏：

• 开始时，他可以任选一个脚手架 i 站上去。

• 如果当前站在脚手架 i，他可以移动到脚手架 j，当且仅当满足：

  • 1 ≤ |i - j| ≤ R
  • H_j ≤ H_i - D

也就是说：

• 目标脚手架与当前位置的距离 不超过 R 且不为 0 。
• 目标脚手架的高度 至少比当前脚手架低 D 。

高桥会不断移动，直到 无法再进行合法移动为止 。求他最多可以移动多少次。

Constraints#

• $1 \leq N \leq 5 × 10^5$
• $1 \leq D, R \leq N$

Input#

输入包含两行：

• 第一行包含三个整数 $N$ 、$D$ 、$R$ 。
• 第二行包含 $N$ 个整数 $H_i$ ，表示数组元素。

$N \quad D \quad R$

$H_1 \quad H_2 \quad \ldots \quad H_N$

Output#

输出一个整数，表示最多可以进行的移动次数。

Sample Input 1#

5 2 1
5 3 1 4 2

Sample Output 1#

2

Sample Input 2#

13 3 2
13 7 10 1 9 5 4 11 12 2 8 6 3

Sample Output 2#

3

Problem Statement#

对于一个包含 $1$ 到 $n$ 的整数的数组，如果满足 $i < j$ 且 nums[i] > nums[j] ，则称 (i, j) 为一个 逆序对 。

给定两个整数 $n$ 和 $k$ ，请返回满足恰好包含 $k$ 个逆序对的、长度为 $n$ 的数组的个数。由于答案可能很大，请返回答案对 $10^9 + 7$ 取模的结果。

Constraints#

• $1 \leq n \leq 1000$
• $0 \leq k \leq 1000$

Input#

输入仅包含一行：

$n \quad k$

Output#

输出一个整数，表示满足条件的数组个数对 $10^9 + 7$ 取模的结果。

Sample Input 1#

3 0

Sample Output 1#

1

Sample Input 2#

3 1

Sample Output 2#

2