CSP-J 2021 T2 插入排序

本文主要是介绍CSP-J 2021 T2 插入排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门

洛谷 P7910 [CSP-J 2021] 插入排序

算法解析

千万不要题目让你插入排序你就插入排序

首先可以用 $pair$ 来存储元素的值（$first$）和原来的下标（$second$）

再用一个数组 $po{s}_i$ 来记录原来的第 $i$ 个元素现在在第几位

初始化：

scanf("%d%d", &n, &q);for(int i = 1; i <= n; ++i) {scanf("%d", &a[i].first);a[i].second = pos[i] = i;
}

接下来是重点 ！！！

想一下，如果原本序列有序，更改一个数的值，那么一遍冒泡排序就可以维护顺序（即如果它小，则把它往前放，如果它大，则把它往后放，具体请参考代码）

得出函数 $sort$_$once$

void sort_once() {for(int i = 1; i < n; ++i)if(a[i] > a[i + 1]) {swap(pos[a[i].second], pos[a[i + 1].second]);swap(a[i], a[i + 1]);}for(int i = n - 1; i > 0; --i)if(a[i] > a[i + 1]) {swap(pos[a[i].second], pos[a[i + 1].second]);swap(a[i], a[i + 1]);}
}

剩下的就简单了

while(q-- && scanf("%d%d", &op, &x)) {if(op == 1) {scanf("%d", &y);for(int i = 1; i <= n; ++i)if(a[i].second == x) {a[i].first = y;break;}sort_once();} elseprintf("%d\n", pos[x]);
}

总代码

#include <cstdio>
#include <algorithm>
#include <utility>
#define N 10005
using namespace std;int n, q;
pair <int, int> a[N];
int op, x, y;
int pos[N];void sort_once() {for(int i = 1; i < n; ++i)if(a[i] > a[i + 1]) {swap(pos[a[i].second], pos[a[i + 1].second]);swap(a[i], a[i + 1]);}for(int i = n - 1; i > 0; --i)if(a[i] > a[i + 1]) {swap(pos[a[i].second], pos[a[i + 1].second]);swap(a[i], a[i + 1]);}
}int main() {scanf("%d%d", &n, &q);for(int i = 1; i <= n; ++i) {scanf("%d", &a[i].first);a[i].second = pos[i] = i;}for(int i = 1; i <= n; ++i)sort_once();while(q-- && scanf("%d%d", &op, &x)) {if(op == 1) {scanf("%d", &y);for(int i = 1; i <= n; ++i)if(a[i].second == x) {a[i].first = y;break;}sort_once();} elseprintf("%d\n", pos[x]);}return 0;
}

提交记录

提交记录 · 点这里

尾声

如果这篇博客对您（您的团队）有帮助的话，就帮忙点个赞，加个关注！

最后，祝您（您的团队）在 OI 的路上一路顺风！！！

┬┴┬┴┤・ω・)ノ Bye_Bye

这篇关于CSP-J 2021 T2 插入排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---