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

题目链接:P7910 [CSP-J 2021] 插入排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:

1.定义结构体，将输入数据和它是第几位绑定起来。增加一个数组f[x]，记录原来序列中的第x个在新序列中的位置，每执行一次修改操作，我们需要对数组重新排序一次，意味着f[x]要更新一次。

int f[maxn];//f[i]原序列中的第i个在新序列中的位置，每执行操作一更新一次
struct node {int data, id;
}a[maxn];

2.操作二的查询即是将f[x]输出出来。

int x;
cin >> x;
cout << f[x] << endl;

3.每次操作一执行完成数组重新排序一次。两个for循环的原因，这个位置上的数字可能变大可能变小。如果变大需要将其往后冒泡找到他应该在的位置。反之，往前冒泡（我看题解没写这个判断条件，对于本菜鸟很容易造成误导，这里加上了）。

			int x, y;cin >> x >> y;//设置ax=yint tmp = a[f[x]].data;a[f[x]].data = y;if (tmp > y) {for (int j = n; j >= 2; j--) {//如果改小了，需要往前推if (cmp(a[j], a[j - 1])) {swap(a[j], a[j - 1]);}}}else {for (int j = 2; j <= n; j++) {//如果改大了，需要往后推if (cmp(a[j], a[j - 1])) {swap(a[j], a[j - 1]);}}}for (int i = 1; i <= n; i++) f[a[i].id] = i;

完整代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int f[maxn];//f[i]原序列中的第i个在新序列中的位置，每执行操作一更新一次
struct node {int data, id;
}a[maxn];
bool cmp(node n1,node n2) {if (n1.data != n2.data) return n1.data < n2.data;return n1.id < n2.id;//稳定排序
}
int main() {int n, Q;cin >> n >> Q;for (int i = 1; i <= n; i++) {cin >> a[i].data;a[i].id = i;}sort(a + 1, a + 1 + n, cmp);//为了操作2做准备for (int i = 1; i <= n; i++) f[a[i].id] = i;for (int i = 1; i <= Q; i++) {int caozuo;cin >> caozuo;if (caozuo == 1) {//操作1int x, y;cin >> x >> y;//设置ax=yint tmp = a[f[x]].data;a[f[x]].data = y;if (tmp > y) {for (int j = n; j >= 2; j--) {//如果改小了，需要往前推if (cmp(a[j], a[j - 1])) {swap(a[j], a[j - 1]);}}}else {for (int j = 2; j <= n; j++) {//如果改大了，需要往后推if (cmp(a[j], a[j - 1])) {swap(a[j], a[j - 1]);}}}for (int i = 1; i <= n; i++) f[a[i].id] = i;}else {int x;cin >> x;cout << f[x] << endl;}}return 0;
}

---- Last Blog  ----