题解

题面描述

我们有$n$块「记忆碎片」，它们按顺序排列，每块对应的记忆发生时间为$t_i$，且$t_1,t_2,\dots,t_n$构成$1$到$n$的一个排列。目标是将这些碎片重新排列成单调递增的顺序，也就是排序为$1,2,\dots,n$。允许的交换操作必须满足：

• 每次只能交换两块**发生时间相差不超过$k$**的碎片；
• 如果交换的两块碎片的记忆时间差恰好为$1$，则需要消耗$1$点精力（即代价$1$）；
• 如果交换碎片的记忆时间差大于$1$（但不超过$k$），则交换是免费的。

要求计算出在最优策略下恢复记忆所需消耗的最少精力。

思路分析

由于允许交换操作必须满足交换两数差值不超过$k$这一约束，不同的$k$值下可交换的碎片对不同：

1. 当$k\ge3$时：
   考察允许免费交换的条件：

   • 免费交换当$|t_i-t_j|>1$且不超过$k$；
   • 显然当$k\ge3$时，不难证明所有$1,\dots,n$（除了$k=1$和$k=2$这两种特殊情况）都可以通过一系列免费交换将各自移动到正确位置。
     因此当$k\ge3$时，不需要消耗任何精力，答案为$0$。

2. 当$k=1$时：
   此时唯一允许交换的两数必须满足$|t_i-t_j|\le1$，而由于数字均不相同，因此必定有$|t_i-t_j|=1$。
   也就是说只能交换相邻两个数字（记住：对于两个相差$1$的数，无论是否在相邻位置，只要它们能交换就必然消耗$1$点精力，而实际上 $k=1$常常限制我们只能相邻交换）。
   此时题目退化为只能使用代价为$1$的相邻交换来排序，而交换相邻两个数所需的最小交换次数正好等于排序所需的逆序数。
   于是答案即为数组的逆序数（使用树状数组或归并排序均可计数）。

3. 当$k=2$时：
   分析允许交换条件：

   • 允许交换的若两数字满足$|t_i-t_j|=1$，交换时代价为$1$；
   • 若$|t_i-t_j|=2$（在$[2,2]$内），则交换免费。

   注意到：

   • 免费交换仅能在差值为$2$的数之间进行。观察$1,2,3,4,\dots$按大小排列时，可以发现所有奇数之间可以免费交换，所有偶数之间也可以免费交换，而奇数与偶数之间的交换必须消耗精力（因为两数差必为$1$）。
     因此最终有序序列中：
   • 奇数一定出现在奇数位置（如$1,3,5,\dots$）；
   • 偶数一定出现在偶数位置（如$2,4,6,\dots$）。

   由于在同一组内（奇数组和偶数组）可以任意免费排列，我们只需要考虑怎样利用代价为$1$的交换将原序列中奇偶错位的碎片“对调”到正确的位置。

   具体做法：

   • 提取原序列中奇数所处的位置集合$\mathbf{B}$（按从左到右记录位置）；

   • 设奇数的个数为$m$，那么在最终有序序列中，奇数应当出现在位置集合$\mathbf{A}=\{1,3,5,\dots,2m-1\}$；

   • 由于只能通过相邻交换（每次调整位置移动一步，对换一对奇偶）来改变位置，最小消耗的能量等于把$\mathbf{B}$变成$\mathbf{A}$所需的总移动步数，即

     $$\text{答案}=\sum_{i=1}^{m} \big|B_i - (2i-1)\big|.$$

   同理偶数组自然也会对应调整，但一次交换可以同时调整一个奇数和一个偶数，因此上述步数即为最小所需的能量。

综上，不同$k$值对应：

• $k\ge3$：答案为$0$；
• $k=1$：答案为逆序数；
• $k=2$：答案为$$\sum_{i=1}^{\text{奇数个数}} \big|B_i - (2i-1)\big|.$$

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// 树状数组（Binary Indexed Tree），用于计算逆序数
struct BIT {
    int n;
    vector<int> tree;
    BIT(int n): n(n), tree(n+1, 0) {}
    // 更新下标i，增加val
    void update(int i, int val) {
        for(; i <= n; i += i & -i)
            tree[i] += val;
    }
    // 查询前缀和[1, i]
    int query(int i) {
        int res = 0;
        for(; i > 0; i -= i & -i)
            res += tree[i];
        return res;
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k;
    cin >> n >> k;
    vector<int> t(n);
    for (int i = 0; i < n; i++){
        cin >> t[i];
    }
 
    // 根据k值分情况讨论
    if(k >= 3){
        
        cout << 0 << "\n";
    }
    else if(k == 1){
        // 当k = 1时，只能交换相差1的碎片，
        // 这相当于只能进行相邻交换，最少代价等于逆序数
        ll inv = 0;
        BIT bit(n);
        // 逆序数算法：从左到右统计比当前大且出现过的数字个数
        for(int i = 0; i < n; i++){
            // 查询t[i]左侧已有数字中大于t[i]的个数
            inv += i - bit.query(t[i]);
            bit.update(t[i], 1);
        }
        cout << inv << "\n";
    }
    else if(k == 2){
        // 当k = 2时，只能免费交换两个相差2的数字，
        // 这使得所有奇数之间可免费交换，偶数之间可免费交换，
        // 而奇偶之间交换必须付费（代价为1）
        // 故最终有序序列中，奇数必出现在位置1,3,5,.......
        // 偶数必出现在位置2,4,6,......
        // 利用免费交换可以任意调换同组内顺序，
        // 故只需要计算将原排列中奇数移动到预定奇数位置所需的步数即可。
 
        vector<int> posOdd;  // 存储原序列中奇数所在的位置（下标从1开始）
        for (int i = 0; i < n; i++){
            if(t[i] & 1) posOdd.push_back(i+1);
        }
        ll ans = 0;
        // 设奇数个数为m，目标奇数位置为1,3,5,......,2m-1
        for (int i = 0; i < posOdd.size(); i++){
            int target = 2*i + 1;
            ans += abs(posOdd[i] - target);
        }
        cout << ans << "\n";
    }
 
    return 0;
}

Python

# Python解法
import sys
import math

# 读入数据
input_data = sys.stdin.read().strip().split()
if not input_data:
    exit(0)
n = int(input_data[0])
k = int(input_data[1])
t = list(map(int, input_data[2:]))

# 根据k分情况讨论
if k >= 3:
   
    print(0)
elif k == 1:
    # 当k=1时，只允许相差1的交换，即只能进行相邻交换，
    # 最少消耗的能量等于逆序数
    # 使用树状数组计算逆序数
    class BIT:
        def __init__(self, n):
            self.n = n
            self.tree = [0]*(n+1)
        def update(self, i, delta):
            while i <= self.n:
                self.tree[i] += delta
                i += i & -i
        def query(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s
    bit = BIT(n)
    inv = 0
    # 遍历数组并计算逆序数
    for i in range(n):
        # 当前数字t[i]左侧已经出现的数字个数为 bit.query(t[i])
        inv += i - bit.query(t[i])
        bit.update(t[i], 1)
    print(inv)
elif k == 2:
    # 当k=2时，只有相差2的数字可以免费交换，
    # 所有奇数内部可以免费交换，偶数内部可以免费交换，
    # 奇数与偶数之间交换消耗1点能量。
    # 最终有序排列中奇数应出现在位置1,3,5......
    pos_odd = []  # 存储原序列中奇数所在的位置（位置从 1 开始）
    for i in range(n):
        if t[i] % 2 == 1:
            pos_odd.append(i+1)
    ans = 0
    # 目标奇数位置为1,3,5,......, 2m-1
    for i, pos in enumerate(pos_odd):
        target = 2 * i + 1
        ans += abs(pos - target)
    print(ans)

Java

import java.io.*;
import java.util.*;
 
public class Main {
    // 用于树状数组计算逆序数
    static class BIT {
        int n;
        int[] tree;
        public BIT(int n) {
            this.n = n;
            tree = new int[n+1];
        }
        // 更新下标i加val
        void update(int i, int val) {
            for(; i <= n; i += i & -i)
                tree[i] += val;
        }
        // 查询前缀和[1, i]
        int query(int i) {
            int s = 0;
            for(; i > 0; i -= i & -i)
                s += tree[i];
            return s;
        }
    }
 
    public static void main(String[] args) throws IOException {
        // 采用BufferedReader提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split("\\s+");
        int n = Integer.parseInt(parts[0]);
        int k = Integer.parseInt(parts[1]);
 
        String[] tokens = br.readLine().split("\\s+");
        int[] t = new int[n];
        for (int i = 0; i < n; i++){
            t[i] = Integer.parseInt(tokens[i]);
        }
 
        if(k >= 3){
            
            System.out.println(0);
        }
        else if(k == 1){
            // 当 $k = 1$ 时，只能做相邻交换，答案为逆序数
            long inv = 0;
            BIT bit = new BIT(n);
            for(int i = 0; i < n; i++){
                // 左侧已有数字个数为 bit.query(t[i])
                inv += i - bit.query(t[i]);
                bit.update(t[i], 1);
            }
            System.out.println(inv);
        }
        else if(k == 2){
            // 当k = 2时，奇数可以免费交换，偶数可以免费交换，
            // 但奇数与偶数之间交换消耗1点能量。
            // 提取原排列中奇数出现的位置（位置从1开始计）
            ArrayList<Integer> posOdd = new ArrayList<>();
            for (int i = 0; i < n; i++){
                if(t[i] % 2 == 1) {
                    posOdd.add(i+1);
                }
            }
            long ans = 0;
            // 目标奇数位置为1,3,5,......,2m-1
            for (int i = 0; i < posOdd.size(); i++){
                int target = 2 * i + 1;
                ans += Math.abs(posOdd.get(i) - target);
            }
            System.out.println(ans);
        }
    }
}

题目内容

你得到了$n$块「记忆碎片」，它们排成一排，第$i$块碎片所对应记忆发生的时间为$t_i$;。t1,t2,...,tn是1到n的一个排列。

你希望重新排列这$n$块碎片，使它们单调递增(即重排为$1,2,...,n$) ，排列的规则为:

• 你有一个能力值$k$，每次你可以选择两块发生时间相差不超过$k$的碎片，交换它们的顺序;
• 由于发生时间过于靠近的两块碎片很难回想，对于两块发生时间相差恰好为$1$的碎片，交换它们需要消耗你$1$点精力;
• 对于发生时间相差大于$1$的碎片，交换它们则不需要耗费精力。

你想知道你最少需要消耗多少精力才能恢复你的「记忆」。

输入描述

第一行输入两个整数$n,k(4≦n≦2×10^5;1≦k≦n-1)$代表「记忆碎片」的个数、你的能力值。

第二行输入$n$个不同的整数$t_1,t_2,...,t_n (1≦t_i ≦n)$，其中，$t_i$代表第$i$块「记忆碎片」所对应记忆的发生时间。

输出描述

输出一个整数，表示你最少需要消耗的精力。

样例1

输入

4 1
2 1 3 4

输出

1

说明

在这个样例中，交换$t_1$和 $t_2$即可。我们可以证明，最少需要消耗$1$点精力。

样例2

输入

4 3
2 1 3 4

输出

0

说明

最优交换策略为:

• 交换$t_1$和$t_4$,得到{$4,1,3,2$};

• 交换$t_2$和$t_4$,得到{$4,2,3,1$};

• 交换$t_1$和$t_4$,得到{$1,2,3,4$}。

  至此，$t$已经有序，最少需要消耗$0$点精力。