专栏文章

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

HHuangRuibo
B4171题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq4nlmr
此快照首次捕获于
2025/12/03 22:53
3 个月前
此快照最后确认于
2025/12/03 22:53
3 个月前
查看原文

题解

B4171

题目传送门
BCSP-X落榜生的题解

做题思路

我爱 vector
注意：本代码 vector 较多，请自行选择观看。
输入部分(\small( 没啥好说的，看就完了 )\small)
CPP
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];
}
初始化位置数组
CPP
vector<int> pos(n + 1);
for (int i = 0; i < n; ++i) {
pos[arr[i]] = i + 1; // 1-based
}
开干，排序！
知识点: for( : ) 传送门
(注：不是自己的Blog,仅供题解参考,无抄袭/侵权想法)
CPP
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)
CPP
    for (int i = 0; i < n; ++i) {//此处书接上回
        cout << current_arr[i] << " ";
    }
    cout << endl;
}
好·习惯
CPP
  return 0;

AC Code:

CPP
#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

🎉 🎉完结撒花🎉🎉

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...