书架的问题

解题思路:

创建一个visited数组来标记已经访问过的位置

遍历数组，对于每个未访问的位置，开始寻找循环

在循环中，从当前位置开始，按照"当前元素的值应该放在哪个位置"的规则追踪整个循环

对于每个长度为k的循环，需要k-1次交换

将所有循环的交换次数相加得到总的最小交换次数

注意事项:

参考代码:

#include <stdio.h>

#include <stdlib.h>

int minSwaps(int arr[], int n) {

    // 创建位置数组，记录每个编号应该在的位置

    int *pos = (int *)malloc((n + 1) * sizeof(int));

    int *visited = (int *)calloc(n, sizeof(int));

    // 记录每个元素的位置

    for (int i = 0; i < n; i++) {

        pos[arr[i]] = i;

    }

    int swaps = 0;

    for (int i = 0; i < n; i++) {

        // 如果当前位置已经是正确的书，或者已经访问过，则跳过

        if (visited[i] || arr[i] == i + 1) {

            continue;

        }

        // 开始寻找循环

        int cycle_size = 0;

        int j = i;

        while (!visited[j]) {

            visited[j] = 1;

            // 当前元素arr[j]应该放在位置arr[j]-1

            j = pos[j + 1];  // 找下一个位置

            cycle_size++;

        }

        // 对于长度为k的循环，需要k-1次交换

        if (cycle_size > 0) {

            swaps += (cycle_size - 1);

        }

    }

    free(pos);

    free(visited);

    return swaps;

}

int main() {

    int n;

    // 读取输入

    if (scanf("%d", &n) != 1) {

        return 1;

    }

    int *arr = (int *)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {

        if (scanf("%d", &arr[i]) != 1) {

            free(arr);

            return 1;

        }

    }

    // 计算最小交换次数

    int result = minSwaps(arr, n);

    printf("%d\n", result);

    free(arr);

    return 0;

}