PDF文档公众号回复关键字:20241006
1P7910 [CSP-J 2021] 插入排序
[题目描述]
插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。
假设比较两个元素的时间为 O(1)，则插入排序可以以 O(n^2) 的时间复杂度完成长度为 n 的数组的排序。不妨假设这 n个数字分别存储在 a1,a2,…,an之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式
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 次操作，操作共两种，参数分别如下为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业：
H 老师给了一个长度为 n的数组 a，数组下标从 1 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 a上的 Q 次操作，操作共两种，参数分别如下
x v：这是第一种操作，会将 a 的第 x 个元素，也就是 ax 的值，修改为 v。保证 1≤x≤n，1≤v≤10^9。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作
x：这是第二种操作，假设 H 老师按照上面的伪代码对 a 数组进行排序，你需要告诉 H 老师原来 a 的第 x 个元素，也就是 ax，在排序后的新数组所处的位置。保证 1≤x≤n。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作
H 老师不喜欢过多的修改，所以他保证类型 1 的操作次数不超过 5000
小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题
[输入格式]
第一行，包含两个正整数 n,Q，表示数组长度和操作次数。
第二行，包含 n 个空格分隔的非负整数，其中第 i 个非负整数表示 ai
接下来 Q 行，每行 2∼3个正整数，表示一次操作
[输出格式]
对于每一次类型为 2 的询问，输出一行一个正整数表示答案
[输入输出样例]
输入 #1
3 4
3 2 1
2 3
1 3 2
2 2
2 3
输出 #1
1
1
2
说明/提示
在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 3,2,1。
在修改操作之后，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 3,1,2。
注意虽然此时 a2=a3，但是我们不能将其视为相同的元素
数据规模
对于所有测试数据，满足 1≤n≤8000，1≤Q≤2×10^5，1≤x≤n，1≤v, ai≤10^9。
对于所有测试数据，保证在所有 Q 次操作中，至多有 5000 次操作属于类型一
2 相关知识点
1) 排序稳定性
稳定排序
排序后 2 个相等键值的顺序和排序之前它们的顺序相同
不稳定
排序后 2 个相等键值的顺序和排序之前它们的顺序不相同
排序前
排序后
稳定
排序后
不稳定
2) 结构体
结构体属于用户自定义的数据类型，允许用户存储不同的数据类型
例如：
学生有姓名/年龄/分数，其中，姓名和年龄/分数是不同类型，因此不能使用数组准确存储
创建结构体
创建一个新的学生数据类型：学生包括（姓名，年龄，分数）
struct Student{
//成员列表
//姓名
string name;
//年龄
int age;
//分数
int score;
};
声明结构体类型
Student s1;
结构体赋值
s1.name = "张三";
s1.age = 18;
s1.score = 100;
整体示例参考
#include <bits/stdc++.h>
using namespace std;
/*创建学生数据类型
struct 类型名称 { 成员列表 }
*/
struct Student{
//成员列表
//姓名
string name;
//年龄
int age;
//分数
int score;
}S[10];//定义以Student为类型的数组S
int main(){
Student s1; //声明结构体变量
//给s1属性赋值，通过.访问结构体变量中的属性
s1.name = "张三";
s1.age = 18;
s1.score = 100;
cout << "姓名：" << s1.name << "年龄：" << s1.age << "分数：" << s1.score << endl;
Student s2 = { "李四" , 19 , 80 };//声明结构体变量并赋值
cout << "姓名：" << s1.name << "年龄：" << s1.age << "分数：" << s1.score << endl;
//结构体数组
S[0].name = "王五";
S[0].age = 30;
S[0].score = 98;
cout << "姓名：" << S[0].name << "年龄：" << S[0].age << "分数：" << S[0].score << endl;
return 0;
}
3) sort排序
sort是c++ algorithm 库里的一个排序函数，平均时间复杂度为O(n*log n)
基本用法
sort(起始地址，末尾地址+1)；
sort(起始地址，末尾地址+1，cmp)；
#include<iostream>
#include<algorithm> //使用sort等算法函数需要的头文件
using namespace std;
void print(int a[]){//打印函数
for(int i=0;i<10;i++){
cout<<a[i]<<' ';
}
cout<<endl;
}
bool cmp(int a1,int a2){//大于号是升序排序，小于号是降序排序
return a1>a2;
}
int main(){
int a[10]={3,1,4,5,8,0,9,2,7,6};
cout<<"排序前："<<endl;
print(a); //打印
sort(a,a+10);//排序，默认是升序的
cout<<"排序后："<<endl;
print(a); //打印
sort(a,a+10,cmp);//自定义排序
cout<<"自定义降序："<<endl;
print(a);
}
/*
输出
排序前：
3 1 4 5 8 0 9 2 7 6
排序后：
0 1 2 3 4 5 6 7 8 9
自定义降序：
9 8 7 6 5 4 3 2 1 0
*/
4) 计数排序
计数排序（Counting Sort）是一种线性时间复杂度的排序算法，适用于整数排序且待排序的元素范围相对较小的情况。它的基本思想是通过统计每个元素出现的次数，然后根据统计信息将元素放回原数组的正确位置，从而实现排序
例题
如下几个数字进行计数排序
5 6 8 3 2 4
声明数组a[10]={0},分别把上面数字作为a数字下标，值为当前数+1
赋值后数组如下
下标 0 1 2 3 4 5 6 7 8 9
数值 0 0 1 1 1 1 1 0 1 0
逐一输出不为0的数的下标，如果值大于1，输出多次
计数排序，是对哈希直接定址法的变形应用,具体思路为:统计相同元素出现次数,根据统计的结果将序列回收到原来的序列中
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[10]={3,4,2,7,5,4,3,3,3,5};
int cnt[7]={0};//cnt数组记录对应下标出现次数
for(int i=0;i<10;i++){
cnt[a[i]]++;
}
for(int i=0;i<=7;i++){//枚举对应范围的数 从最小到最大，本示例从0~7即可
while(cnt[i]>0){//一个数字出现多次时，cnt[i]为对应的数为出现几次
cout<<i<<" ";
cnt[i]--;
}
}
return 0;
}
/*
输出
2 3 3 3 3 4 4 5 5 7
*/
3 思路分析
思路1
1 多次询问，且中间可能会修改数组
2 每次询问，计算1次排序后的位置
3 计算位置，找出所有比自己小的，即去除前面比自己大的+后比自己小的
示例程序
#include<bits/stdc++.h>
using namespace std;
const int maxN=8010;//数组元素个数
/*
n输入n个数
Q进行q次操作
opt输入操作类型 1 修改 2 询问位置
x 修改的位置 v修改的值
leftCnt修改数前面大于该数的个数
rightCnt修改数后面小于该数的个数
*/
int n,Q,opt,x,v,leftCnt,rightCnt;
int a[maxN];//存储输入数的数组
int main(){
cin>>n>>Q;//输入n个数和Q次操作
for(int i=1;i<=n;i++){//逐一输入n个数
cin>>a[i];
}
for(int i=1;i<=Q;i++){//逐一输入和处理Q次操作
cin>>opt;//输入操作类型 修改
if(opt==1){
cin>>x>>v;//输入修改位置x和修改数v
a[x]=v;//修改x位置的数为v
}
if(opt==2){//询问
cin>>x;//输入x在排序后的位置
leftCnt=rightCnt=0;//初始为0
for(int i=1;i<x;i++){//x位置前面的大的累加
if(a[i]>a[x]){
leftCnt++;
}
}
for(int i=x+1;i<=n;i++){//x位置后面小的累加
if(a[i]<a[x]){
rightCnt++;
}
}
//当前位置:去除前面大的+上后面小的
cout<<x-leftCnt+rightCnt<<endl;
}
}
}
由于此思路花费时间主要在询问位置时，询问位置的次数在2*10^5-5000左右，每次询问时间复杂度为O(n),n最大为8000，因此肯定会超时
思路2
1 由于修改次数比较少，每次修改后计算所有元素排序后位置
2 使用结构体，记录元素在原数组的下标
3 先对数组进行排序，使用t数组通过计数排序记录原数组元素，在排序后数组的位置
4 修改原数组下标x在排序后数组中的值，并对x左边进行排序，对应x右边进行排序，使整个数组有序
5 排序后重新维护t数组
6 询问x位置时，直接输出t[x]
示例程序
#include<bits/stdc++.h>
using namespace std;
const int maxN=8010;//数组元素个数
/*
结构体 id 输入的原始位置
num 输入的数
*/
struct node{
int id;
int num;
}a[maxN];//存储待排序数
/*
t[i] 原数字i位置在排序后数组的中的位置
n 输入结果数
Q 进行操作次数
*/
int t[maxN],n,Q;
/*
opt输入操作类型 1 修改 2 询问位置
x 修改的位置 v修改的值
*/
int opt,x,v;
/*
比较函数
按结构体node 中num从小到大排序
node1.num<node2.num return true
如果num相同，按结构体node中id从小到大排序
node1.id<node2.id return true
*/
bool cmp(node node1,node node2){
if(node1.num!=node2.num){
return node1.num<node2.num;
}else{
return node1.id<node2.id;
}
}
int main(){
cin>>n>>Q;//输入n个数和Q次操作
for(int i=1;i<=n;i++){//逐一输入n个数
cin>>a[i].num;
a[i].id=i;
}
/*
按结构体node 中num从小到大排序
如果num相同，按结构体node中id从小到大排序
*/
sort(a+1,a+n+1,cmp);
//初始原数组对应数在排序后数组中的位置
for(int i=1;i<=n;i++){
t[a[i].id]=i;
}
for(int i=1;i<=Q;i++){//Q次操作
cin>>opt;//输入操作类型
if(opt==1){//修改
cin>>x>>v;//输入修改位置x和修改数v
a[t[x]].num=v;//修改x位置的数为v
/*
如果修改数位置后面有比v小的数
逐一交换，保证从小到大排序
*/
for(int j=t[x];j<n;j++){
if(cmp(a[j+1],a[j])){
node tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
/*
如果修改数位置前面有比v大的数
逐一交换，保证从小到大排序
*/
for(int j=t[x];j>1;j--){
if(cmp(a[j],a[j-1])){
node tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
}
}
//逐一把原数组元素位置对应新数组位置
for(int j=1;j<=n;j++){
t[a[j].id]=j;
}
}
if(opt==2){//操作为询问
cin>>x;//输入询问位置
cout<<t[x]<<endl;//输出在新数组中位置
}
}
return 0;
}
思路2的优化思路，把每次询问计算逻辑改动每次修改后进行计算存储，修改的次数最多为5000，O(n)的时间复杂度不会超时
每次询问时直接从数组读取，时间复杂度为O(1),效率明显提升
思路2读入优化
在思路2基础上，使用scanf代替cin，大数据读入时，效率提升40%~50%
示例程序
#include<bits/stdc++.h>
using namespace std;
const int maxN=8010;//数组元素个数
/*
结构体 id 输入的原始位置
num 输入的数
*/
struct node{
int id;
int num;
}a[maxN];//存储待排序数
/*
t[i] 原数字i位置在排序后数组的中的位置
n 输入结果数
Q 进行操作次数
*/
int t[maxN],n,Q;
/*
opt输入操作类型 1 修改 2 询问位置
x 修改的位置 v修改的值
*/
int opt,x,v;
/*
比较函数
按结构体node 中num从小到大排序
node1.num<node2.num return true
如果num相同，按结构体node中id从小到大排序
node1.id<node2.id return true
*/
bool cmp(node node1,node node2){
if(node1.num!=node2.num){
return node1.num<node2.num;
}else{
return node1.id<node2.id;
}
}
int main(){
scanf("%d%d",&n,&Q);//cin>>n>>Q;//输入n个数和Q次操作
for(int i=1;i<=n;i++){//逐一输入n个数
scanf("%d",&a[i].num);//cin>>a[i].num;
a[i].id=i;
}
/*
按结构体node 中num从小到大排序
如果num相同，按结构体node中id从小到大排序
*/
sort(a+1,a+n+1,cmp);
//初始原数组对应数在排序后数组中的位置
for(int i=1;i<=n;i++){
t[a[i].id]=i;
}
for(int i=1;i<=Q;i++){//Q次操作
scanf("%d",&opt);//cin>>opt;//输入操作类型
if(opt==1){//修改
scanf("%d%d",&x,&v);//cin>>x>>v;//输入修改位置x和修改数v
a[t[x]].num=v;//修改x位置的数为v
/*
如果修改数位置后面有比v小的数
逐一交换，保证从小到大排序
*/
for(int j=t[x];j<n;j++){
if(cmp(a[j+1],a[j])){
node tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
/*
如果修改数位置前面有比v大的数
逐一交换，保证从小到大排序
*/
for(int j=t[x];j>1;j--){
if(cmp(a[j],a[j-1])){
node tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
}
}
//逐一把原数组元素位置对应新数组位置
for(int j=1;j<=n;j++){
t[a[j].id]=j;
}
}
if(opt==2){//操作为询问
scanf("%d",&x);//cin>>x;//输入询问位置
printf("%d\n",t[x]);//cout<<t[x]<<endl;//输出在新数组中位置
}
}
return 0;
}
读入优化后，效率进一步提升，可以观察其中测试用例，从323ms下降到201ms
