Swirly Sort
给定一个包含 n 个整数的数组 A,以及整数 k(1≤k≤n)。你希望把数组变成有序数组。
你可以执行任意多次下列两种操作:
- 选择 k 个下标 1≤i1<i2<⋯<ik≤n,将这些位置上的值循环移动:原来的 A[i1] 移到位置 i2,原来的 A[i2] 移到位置 i3,依此类推,原来的 A[ik] 移到位置 i1。所选下标必须按递增顺序排列。这次操作的费用为 0。
- 选择一个下标 i,把 A[i] 增加 1 或减少 1。这次操作的费用为 1。
求使数组有序所需的最小总费用。
数组下标从 1 开始。这里“有序”指非降,即 X1≤X2≤⋯,允许相等元素。
输入格式
第一行包含整数 t,表示测试用例数。
每个测试用例包含两行:第一行是整数 n,k;第二行是数组初始值 A1,…,An。
- 1≤t≤105。
- 1≤n≤3⋅105。
- 1≤k≤n。
- 1≤Ai≤109,这是数组初始值的限制。
- 一份输入中,所有测试用例的 n⋅k 之和不超过 3⋅105。
输出格式
每个测试用例输出一行,一个整数,表示最小总费用。
完整原样例
输入:
4
4 1
6 4 3 7
4 2
6 4 3 7
4 3
6 4 3 7
4 4
6 4 3 7
输出:
3
0
1
2
原样例说明
四个测试用例的初始数组均为 [6,4,3,7]。
- k=1:将第一个元素减去 2,第三个元素加上 1,得到 [4,4,4,7],费用为 3。
- k=2:选择 i1=1,i2=3,免费得到 [3,4,6,7],费用为 0。
- k=3:选择下标 1,2,3 循环移动,得到 [3,6,4,7];再对同样下标循环移动,得到 [4,3,6,7];最后把第一个元素减去 1,得到 [3,3,6,7]。总费用为 1。
- k=4:把第一个元素加上 1,得到 [7,4,3,7];把第二个元素减去 1,得到 [7,3,3,7];依次对全部四个位置循环移动三次,得到 [7,7,3,3]、[3,7,7,3]、[3,3,7,7]。总费用为 2。