题解
题面描述
我们有n块「记忆碎片」，它们按顺序排列，每块对应的记忆发生时间为ti，且t1,t2,…,tn构成1到n的一个排列。目标是将这些碎片重新排列成单调递增的顺序，也就是排序为1,2,…,n。允许的交换操作必须满足：
- 每次只能交换两块**发生时间相差不超过k**的碎片；
- 如果交换的两块碎片的记忆时间差恰好为1，则需要消耗1点精力（即代价1）；
- 如果交换碎片的记忆时间差大于1（但不超过k），则交换是免费的。
P2828.第3题-记忆碎片
题目内容
你得到了n块「记忆碎片」，它们排成一排，第i块碎片所对应记忆发生的时间为ti;。t1,t2,...,tn是1到n的一个排列。
你希望重新排列这n块碎片，使它们单调递增(即重排为1,2,...,n) ，排列的规则为:
- 你有一个能力值k，每次你可以选择两块发生时间相差不超过k的碎片，交换它们的顺序;
- 由于发生时间过于靠近的两块碎片很难回想，对于两块发生时间相差恰好为1的碎片，交换它们需要消耗你1点精力;
- 对于发生时间相差大于1的碎片，交换它们则不需要耗费精力。
你想知道你最少需要消耗多少精力才能恢复你的「记忆」。
输入描述
第一行输入两个整数n,k(4≦n≦2×105;1≦k≦n−1)代表「记忆碎片」的个数、你的能力值。
第二行输入n个不同的整数t1,t2,...,tn(1≦ti≦n)，其中，ti代表第i块「记忆碎片」所对应记忆的发生时间。
输出描述
输出一个整数，表示你最少需要消耗的精力。
样例1
输入
4 1
2 1 3 4
输出
1
说明
在这个样例中，交换t1和 t2即可。我们可以证明，最少需要消耗1点精力。
样例2
输入
4 3
2 1 3 4
输出
0
说明
最优交换策略为:
-
交换t1和t4,得到{4,1,3,2};
-
交换t2和t4,得到{4,2,3,1};
-
交换t1和t4,得到{1,2,3,4}。
至此，t已经有序，最少需要消耗0点精力。
