题目理解

给定长度为 $2n$ 的字符串 $S$，通过交换相邻字符，使得前 $n$ 个字符与后 $n$ 个字符完全相同（顺序可以不同）。求最小交换次数。

核心思路

关键观察：相邻交换次数等于逆序对数。

算法步骤：

1. 将字符串分成前后两半，各长 $n$
2. 对每个字母，建立从前半到后半的匹配
3. 构造匹配数组并计算逆序对数

代码实现

#include <iostream>
#include <vector>
#include <string>
using namespace std;

typedef long long ll;

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n) : n(n), bit(n + 1) {}
    void update(int i) {
        for (; i <= n; i += i & -i) bit[i]++;
    }
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += bit[i];
        return sum;
    }
};

int main() {
    int n;
    string s;
    cin >> n >> s;
    
    vector<vector<int>> pos(26);
    // 记录后半部分每个字符的位置（编号1~n）
    for (int i = n; i < 2 * n; i++) {
        pos[s[i] - 'a'].push_back(i - n + 1);
    }
    
    vector<int> cnt(26, 0);
    vector<int> match(n);
    
    // 建立匹配：前半第i个字符匹配后半第cnt[c]个相同字符
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        match[i] = pos[c][cnt[c]++];
    }
    
    // 树状数组计算逆序对
    Fenwick fenw(n);
    ll ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        ans += fenw.query(match[i] - 1);
        fenw.update(match[i]);
    }
    
    cout << ans << endl;
    return 0;
}

样例分析

样例1

输入：3, koeeok
前半：k o e
后半：e o k
匹配：k→k(3), o→o(2), e→e(1)
匹配数组：[3,2,1]
逆序对：(3,2),(3,1),(2,1) = 3
输出：3

样例2

输入：3, kekoeo
输出：1

样例3

输入：4, soolnlsn
输出：4

复杂度分析

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$

该算法利用树状数组高效计算逆序对，能够处理 $n \leq 10^5$ 的大规模数据。