2021 csp-j t2 插入排序

2021 csp-j t2 插入排序

题目洛谷链接
插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为O(1)，则插入排序可以以O(n^2)的时间复杂度完成长度为 n 的数组的排序。不妨假设这 n 个数字分别存储在 a1, a2，…，an 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：

这下面是 C/C++ 的示范代码：

for (int i = 1; i <= n; i++)for (int j = i; j >= 2; j--)if (a[j] < a[j-1]) {int t = a[j-1];a[j-1] = a[j];a[j] = t;}

为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业：

H 老师给了一个长度为 n 的数组 a，数组下标从 1 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 a 上的 Q 次操作，操作共两种，参数分别如下：

1，1 x v：这是第一种操作，会将 a 的第 x 个元素，也就是 ax
​
的值，修改为 vv。保证 1<=x<=n，1<=v<=10⁹ 。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。

2，2 x：这是第二种操作，假设 H 老师按照上面的伪代码对 a 数组进行排序，你需要告诉 H 老师原来 a 的第 x 个元素，也就是 ax，在排序后的新数组所处的位置。保证 1<=x<=n。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。

H 老师不喜欢过多的修改，所以他保证类型 1 的操作次数不超过 5000。

小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。

#include
#define maxl 8005
using namespace std;
struct  Node{int val,id;//val记值，id记原编号 
}node[maxl];
bool operator < (const Node &x,const Node &y)//重载 < 
{if(x.val!=y.val){return x.val (const Node &x,const Node &y)//重载 >
{if(x.val!=y.val){return x.val>y.val;}return x.id>y.id;
}
int n,q,pos[maxl];//pos[i]记录现位置,i为原数组中的下标 
int main()
{scanf("%d%d",&n,&q);//输入 n,q for(int i=1;i<=n;i++)//输入数组 {scanf("%d",&node[i].val);node[i].id=i;}sort(node+1,node+1+n);for(int i=1;i<=n;i++){pos[node[i].id]=i;}for(int i=1;i<=q;i++){int opt,x,v;//x为原数组的下标 scanf("%d",&opt);if(opt==1)//操作一,对改变的值重排序 {scanf("%d%d",&x,&v);if(node[pos[x]].val>v){node[pos[x]].val=v;for(int j=pos[x];j>1;j--){if(node[j]node[j+1]){swap(pos[node[j].id],pos[node[j+1].id]);swap(node[j],node[j+1]);}else break;}}}else//操作二 {scanf("%d",&x);printf("%d\n",pos[x]);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！