A1523 [BCSP-X2024上.小高2] 选择排序

#include <bits/stdc++.h>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n), pos(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    vector<int> q(m);
    for (int &x : q) cin >> x;

    // 第 i 趟（1 起）要把后缀最小值换到第 i 位。A 是排列，最小值就是 i
    int done = 0;
    for (int i = 0; i < m; ++i) {
        while (done < q[i]) {
            ++done;
            int p = pos[done];
            int other = a[done - 1];
            swap(a[done - 1], a[p]);
            pos[done] = done - 1;
            pos[other] = p;
        }
        for (int j = 0; j < n; ++j) cout << a[j] << (j + 1 == n ? '\n' : ' ');
    }
    return 0;
}