题解：P12176 [蓝桥杯 2025 省 Python B] 书架还原

Iloveyou520 · 2025-04-19 19:25:14 · 题解

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

int minSwaps(vector<int>& books) {
    int n = books.size();
    vector<bool> visited(n, false);
    int swaps = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i] && books[i] != i + 1) {
            int cycle_size = 0;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = books[j] - 1;
                cycle_size++;
            }
            if (cycle_size > 0) {
                swaps += (cycle_size - 1);
            }
        }
    }
    return swaps;
}

int main() {
    int n;
    cin >> n;
    vector<int> books(n);
    for (int i = 0; i < n; ++i) {
        cin >> books[i];
    }
    cout << minSwaps(books) << endl;
    return 0;
}

代码解释

‌输入处理‌：

读取书的数量 n 和当前排列顺序 books 。

‌标记数组‌：