洛谷 CF474E · 难度 提高+/省选−

题目描述

土拨鼠发现了一排有 $n$ 根柱子，第 $i$ 根柱子的高度为 $h_i$ 米。土拨鼠从某一根柱子 $i_1$ 出发，想要依次跳到柱子 $i_2$，...，$i_k$ 上（满足 $1\le i_1<i_2<...<i_k\le n$）。土拨鼠可以从第 $i$ 根柱子跳到第 $j$ 根柱子，当且仅当 $i<j$ 且 $|h_i-h_j|\ge d$，其中 $|x|$ 表示 $x$ 的绝对值。

现在土拨鼠想让你帮他找出一条跳跃序列，使得序列长度最大，并输出这条序列。

输入格式

第一行包含两个整数 $n$ 和 $d$，其中 $1\le n\le {10}^5$，$0\le d\le {10}^9$。

第二行包含 $n$ 个数 $h_1,h_2,...,h_n$，其中 $1\le h_i\le {10}^{15}$。

输出格式

第一行输出一个整数 $k$，表示跳跃序列的最大长度。

第二行输出 $k$ 个整数 $i_1,i_2,...,i_k$，表示该最大长度跳跃序列中柱子的下标（满足 $1\le i_1<i_2<...<i_k\le n$）。

如果存在多条最大长度的跳跃序列，输出任意一条即可。

说明/提示

在第一个样例中，土拨鼠选择了第 $1,2,3,5$ 根柱子，高度分别为 $1,3,6,4$。另一种长度为 $4$ 的跳跃序列是 $1,2,4,5$。

由 ChatGPT 5 翻译

样例

样例 1

输入

5 2
1 3 6 7 4

输出

4
1 2 3 5

样例 2

输入

10 3
2 1 3 6 9 11 7 3 20 18

输出

6
1 4 6 7 8 9