题解：B4171 [BCSP-X 2024 6 月小学高年级组] 选择排序

· · 题解

题解

B4171

题目传送门

BCSP-X落榜生的题解

做题思路

我爱 vector

注意：本代码 vector 较多，请自行选择观看。

输入部分\small( 没啥好说的，看就完了 \small)

int n, m;
cin >> n >> m;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
    cin >> arr[i];
}
vector<int> queries(m);
for (int i = 0; i < m; ++i) {
    cin >> queries[i];
}

初始化位置数组

vector<int> pos(n + 1);
for (int i = 0; i < n; ++i) {
pos[arr[i]] = i + 1; // 1-based
}

开干，排序！

知识点: for( : ) 传送门

(注：不是自己的Blog,仅供题解参考,无抄袭/侵权想法)

for (int q : queries) {
    while (processed < q) {
        processed++;
        int i = processed;
        int current_i = i;
        int current_pos = pos[current_i];
        if (current_pos >= i) {
        // 交换 current_arr[i-1] 和 current_arr[current_pos-1]
        int x = current_arr[i - 1];
        int y = current_arr[current_pos - 1];
        swap(current_arr[i - 1], current_arr[current_pos - 1]);
        // 更新 pos 数组
        pos[x] = current_pos; // x被交换到了原current_pos的位置
        pos[y] = i;           // y被交换到了i的位置
            }
    }

输出！Output！\small( 跟输入部分一样，没啥好说的，看就完了 \small)

    for (int i = 0; i < n; ++i) {//此处书接上回
        cout << current_arr[i] << " ";
    }
    cout << endl;
}

好·习惯

  return 0;

AC Code:

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    vector<int> queries(m);
    for (int i = 0; i < m; ++i) {
        cin >> queries[i];
    }

    // 初始化位置数组
    vector<int> pos(n + 1);
    for (int i = 0; i < n; ++i) {
        pos[arr[i]] = i + 1; // 1-based
    }

    vector<int> current_arr = arr;
    int processed = 0;

    for (int q : queries) {
        while (processed < q) {
            processed++;
            int i = processed;
            int current_i = i;
            int current_pos = pos[current_i];
            if (current_pos >= i) {
                // 交换 current_arr[i-1] 和 current_arr[current_pos-1]
                int x = current_arr[i - 1];
                int y = current_arr[current_pos - 1];
                swap(current_arr[i - 1], current_arr[current_pos - 1]);
                // 更新 pos 数组
                pos[x] = current_pos; // x被交换到了原current_pos的位置
                pos[y] = i;           // y被交换到了i的位置
            }
        }
        // 输出当前的数组
        for (int i = 0; i < n; ++i) {
            cout << current_arr[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

AC Record

🎉 🎉完结撒花🎉🎉