一、题意

输入1 ~ n 的一个排列（n<=500），每次可以交换两个整数，输出至少要用多少次交换，就可以把排列变成一个1 ~ n 的环状排列。

二、解析

由于n比较小，因此暴力模拟法即可。
首先枚举目标排列，总共 2 * n 种（以每一个下标作为开头1、顺时针和逆时针），然后对于每一个目标排列，计算从原始排列a[maxn]到目标排列需要交换的次数。然后取所有次数的最小值即为答案。

为了快速定位原始排列中某些元素的位置，我们可以用一个额外的pos[maxn]来记录元素位置，然后每次模拟交换元素时，同时交换相应的pos数组中的值即可。

三、代码

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 500 + 5, INF = 1 << 30;
int n, a[maxn];

int solve(int offset, int direct) {
    static int temp[maxn], pos[maxn];
    memcpy(temp, a, sizeof(int) * (n + 1));
    for(int i = 1; i <= n; i ++) pos[temp[i]] = i;
    int res = 0;
    for(int i = 0; i < n; i ++) {
        int num = (offset + direct * i + n) % n + 1, pos1 = pos[num], pos2 = i + 1;
        if(pos1 != pos2) {  // 模拟时temp数组和pos数组都要进行交换
            res ++;
            swap(temp[pos1], temp[pos2]);
            swap(pos[temp[pos1]], pos[temp[pos2]]);
        }
    }
    return res;
}

int main() {
    while(cin >> n && n) {
        for(int i = 1; i <= n; i ++) cin >> a[i];
        int ans = INF;
        for(int i = 0; i < n; i ++) ans = min(min(ans, solve(i, 1)), solve(i, -1));  // 注意顺逆时针都要考虑
        cout << ans << endl;
    }
}

四、归纳

  • 还是那句话：时间允许的情况下，算法怎么暴力怎么来
  • 维护pos数组是一种很常见的技巧