前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【题解】[CSP-J 2021] 插入排序

【题解】[CSP-J 2021] 插入排序

作者头像
fishhh
发布2022-10-04 19:29:39
4420
发布2022-10-04 19:29:39
举报
文章被收录于专栏:OI算法学习笔记

[CSP-J 2021] 插入排序

题目描述

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

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

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

代码语言:javascript
复制
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;
		}

这下面是 Pascal 的示范代码:

代码语言:javascript
复制
for i:=1 to n do
	for j:=i downto 2 do
		if a[j]<a[j-1] then
			begin
				t:=a[i];
				a[i]:=a[j];
				a[j]:=t;
			end;

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

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

1 x v1~x~v1 x v:这是第一种操作,会将 aaa 的第 xxx 个元素,也就是 axa_xax​ 的值,修改为 vvv。保证 1≤x≤n1 \le x \le n1≤x≤n,1≤v≤1091 \le v \le 10^91≤v≤109。注意这种操作会改变数组的元素,修改得到的数组会被保留,也会影响后续的操作

2 x2~x2 x:这是第二种操作,假设 H 老师按照上面的伪代码对 aaa 数组进行排序,你需要告诉 H 老师原来 aaa 的第 xxx 个元素,也就是 axa_xax​,在排序后的新数组所处的位置。保证 1≤x≤n1 \le x \le n1≤x≤n。注意这种操作不会改变数组的元素,排序后的数组不会被保留,也不会影响后续的操作

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

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

输入格式

第一行,包含两个正整数 n,Qn, Qn,Q,表示数组长度和操作次数。

第二行,包含 nnn 个空格分隔的非负整数,其中第 iii 个非负整数表示 aia_iai​。

接下来 QQQ 行,每行 2∼32 \sim 32∼3 个正整数,表示一次操作,操作格式见【题目描述】。

输出格式

对于每一次类型为 222 的询问,输出一行一个正整数表示答案。

样例 #1

样例输入 #1

代码语言:javascript
复制
3 4
3 2 1
2 3
1 3 2
2 2
2 3

样例输出 #1

代码语言:javascript
复制
1
1
2

提示

【样例解释 #1】

在修改操作之前,假设 H 老师进行了一次插入排序,则原序列的三个元素在排序结束后所处的位置分别是 3,2,13, 2, 13,2,1。

在修改操作之后,假设 H 老师进行了一次插入排序,则原序列的三个元素在排序结束后所处的位置分别是 3,1,23, 1, 23,1,2。

注意虽然此时 a2=a3a_2 = a_3a2​=a3​,但是我们不能将其视为相同的元素

【样例 #2】

见附件中的 sort/sort2.insort/sort2.ans

该测试点数据范围同测试点 1∼21 \sim 21∼2。

【样例 #3】

见附件中的 sort/sort3.insort/sort3.ans

该测试点数据范围同测试点 3∼73 \sim 73∼7。

【样例 #4】

见附件中的 sort/sort4.insort/sort4.ans

该测试点数据范围同测试点 12∼1412 \sim 1412∼14。

【数据范围】

对于所有测试数据,满足 1≤n≤80001 \le n \le 80001≤n≤8000,1≤Q≤2×1051 \le Q \le 2 \times {10}^51≤Q≤2×105,1≤x≤n1 \le x \le n1≤x≤n,1≤v,ai≤1091 \le v,a_i \le 10^91≤v,ai​≤109。

对于所有测试数据,保证在所有 QQQ 次操作中,至多有 500050005000 次操作属于类型一。

各测试点的附加限制及分值如下表所示。

测试点

n≤n \len≤

Q≤Q \leQ≤

特殊性质

1∼41 \sim 41∼4

101010

101010

5∼95 \sim 95∼9

300300300

300300300

10∼1310 \sim 1310∼13

150015001500

150015001500

14∼1614 \sim 1614∼16

800080008000

800080008000

保证所有输入的 ai,va_i,vai​,v 互不相同

17∼1917 \sim 1917∼19

800080008000

800080008000

20∼2220 \sim 2220∼22

800080008000

2×1052 \times 10^52×105

保证所有输入的 ai,va_i,vai​,v 互不相同

23∼2523 \sim 2523∼25

800080008000

2×1052 \times 10^52×105

分析

阅读题面,可知题目要我们输出的是原来aaa 的第xxx个元素,也就是axa_xax​ ,在排序后的新数组所处的位置。

题目中除了查询操作以外还有一个操作为修改操作:将 aaa 的第 xxx 个元素,也就是 axa_xax​ 的值,修改为 vvv。

其中,修改操作会改变原数组的内容,且修改的是原数列位置上的内容,并修改内容会被保留下来。意味着元素修改可能就会影响数列的排序。

暴力思路

保留原序列aaa,开一个数组bbb,每次修改在原序列aaa上进行修改;查询时,则将aaa中存储到bbb中,对数列bbb

进行排序,再输出axa_xax​在排序后的位置即可。

注意相同值但不同位置元素不能视为相同的元素,所以排序时要注意保持原序列相同元素值的相对位置。

代码语言:javascript
复制
bool cmp(node x,node y){
	if(x.v!=y.v) return x.v<y.v;
	return x.id<y.id;
}

分析下复杂度为O(Qnlogn)O(Qnlogn)O(Qnlogn)。此时数据范围最大n≤8000,Q≤2×105n \le8000,Q\leq 2\times10^5n≤8000,Q≤2×105 ,会超时。得到52分。

优化1.0

思考程序中哪块耗时较多?可发现是在查询时,每次都需要O(nlogn)O(nlogn)O(nlogn)的复杂度进行排序,这块用时较长。在这思考如何优化该过程。我们的目的是找到axa_xax​的位置即可,实际上不需要你去将其他元素排序好,此时只需盯着axa_xax​即可,统计在整个序列中排在它前面的元素有几个,就能知道它在第几个位置了。

代码语言:javascript
复制
	scanf("%d",&x);
    int cnt=0;
    for(int j=1;j<=n;j++){
        if(cmp(a[j],a[x])){
            cnt++;
        }
    }
    printf("%d\n",cnt+1);

分析下复杂度为O(Qn)O(Qn)O(Qn)。比之前的小,但是还是会超时。得到76分。

优化2.0

此时再仔细分析下,注意题目中的数据范围“对于所有测试数据,保证在所有 QQQ 次操作中,至多有 500050005000 次操作属于类型一。”操作类型一为修改操作,类型二维查询操作。之前每次都是O(n)O(n)O(n)的复杂度确定元素位置,O(1)O(1)O(1)的复杂度进行修改。查询的操作比较多,若能再次降低查询时的复杂度,就能优化整体的时间了。

可发现,修改操作远少于查询的操作,若针对一个有序的数列查找原来元素的当前位置关系,这是可以较方便的构建映射关系的。

代码语言:javascript
复制
//site[x]:原序列a[x]在排好后的位置
for(int i=1;i<=n;i++){
    site[a[i].id]=i;
}

我们在执行完操作一,修改完原序列中的元素值之后,再把序列排序下,然后再重新构建位置关系。把用时长的执行的次数少些。

此时还是只有76,因为对于n来说范围也是达到了800080008000的500050005000操作一依然会超。因为排序用时为O(nlogn)O(nlogn)O(nlogn) 。

优化3.0

实际可发现,我们每次修改只更改了一个元素的值,也就是说,剩余元素在整体上是有序的,对于大部分都是有序的数据可以使用插入排序进行优化。我们可以将修改后的元素,插入到n−1n-1n−1个有序元素中。排序复杂度就能降为O(n)O(n)O(n),这样就能满足要求了。

代码语言:javascript
复制
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,q;
struct node{
	int id,val;
}a[8005];
int site[8005];//site[x] 原数列的第x个元素的当前位置
/*
3 2 1
2 3   => 1
1 3 2 =>3 2 2
2 2  1
2 3 2
*/
bool cmp(node x,node y){
	return x.val!=y.val?x.val<y.val:x.id<y.id;
}

//修改
void upd(int x,int v){
	a[site[x]].val=v;//修改原数列中的值
	node key=a[site[x]];
	//往前挪删除原序列a[x] ,使得剩下n-1个元素为有序
	for(int i=site[x]+1;i<=n;i++){
		a[i-1]=a[i];
	}
	
	a[n]=key;//把修改后的值放到最后
	for(int i=n;i>1;i--){//插入 更新的值
		if(!cmp(a[i-1],a[i])){
			swap(a[i-1],a[i]);
		}
	}
	
	//更新site
	for(int i=1;i<=n;i++){
		site[a[i].id]=i;
	}
}
int main(){
	int k,x,v;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].val);
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);//提前排序
	for(int i=1;i<=n;i++){//更新位置关系
		site[a[i].id]=i;
	}
	for(int i=1;i<=q;i++){
		scanf("%d",&k);
		if(k==2){
			scanf("%d",&x);
			printf("%d\n",site[x]);//输出位置
		}else if(k==1){
			scanf("%d%d",&x,&v);
			upd(x,v);//更新
		}
	}
	return 0;
}

Q.E.D.

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • [CSP-J 2021] 插入排序
    • 题目描述
      • 输入格式
        • 输出格式
          • 样例 #1
            • 样例输入 #1
            • 样例输出 #1
          • 提示
            • 分析
              • 暴力思路
              • 优化1.0
              • 优化2.0
              • 优化3.0
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档