2021 插入排序 · 方案一每次真排一遍

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 1558 字

跑一趟稳定插入排序再找目标位置

2021
排序

正文

// CSP-J 2021 复赛 T2 · 插入排序
// 原题：https://oj.yecheng.tv/p/CSPJ2021B
// 题意：一个长度为 n 的序列，两种操作：把某个位置的值改掉；
// 或者问「如果现在做一次插入排序，原来第 x 个元素会排到第几个位置」。
// 注意：值相同的元素也算不同元素，所以这个插入排序是稳定的 ——
//       结果等价于按 (值, 原来位置) 从小到大排。
//
// 方案一 · 每次询问真跑一次插入排序（直观，Q 大时会超时）
// 把下标 1..n 装进数组，跑一趟插入排序：
// 每次把当前元素往前挪，直到前面那个元素不再比它大为止。
// 相等时比较原下标，保证稳定。排完找 x 落在哪个位置。
// 每次询问 O(n^2)，Q 到 2e5 时完全来不及 —— 但它把题意说得最清楚。

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

const int MAXN = 8005;
int a[MAXN];

int main() {
    freopen("sort.in", "r", stdin);
    freopen("sort.out", "w", stdout);

    int n, Q;
    cin >> n >> Q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    while (Q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, v;
            cin >> x >> v;
            a[x] = v;
        } else {
            int x;
            cin >> x;
            vector<int> ids(n);
            for (int i = 0; i < n; i++) ids[i] = i + 1;
            for (int i = 1; i < n; i++) {
                int key = ids[i];
                int j = i - 1;
                while (j >= 0) {
                    int u = ids[j];
                    bool after = (a[u] > a[key]) || (a[u] == a[key] && u > key);
                    if (!after) break;
                    ids[j + 1] = u;
                    j--;
                }
                ids[j + 1] = key;
            }
            for (int i = 0; i < n; i++) {
                if (ids[i] == x) {
                    cout << i + 1 << "\n";
                    break;
                }
            }
        }
    }
    return 0;
}

2021 插入排序 · 方案一 每次真排一遍

正文

CSP-J 标程 · 复赛真题的其它内容

2021 插入排序 · 方案一每次真排一遍