插入排序(CSP-J 2021 T2)
2022/7/29 23:23:16
本文主要是介绍插入排序(CSP-J 2021 T2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:(由于题干过长直接上链接:P7910 [CSP-J 2021] 插入排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)) 不是打广告
又有一个新思路:
我们可以再开一个b数组用来记录第i个数排序后的位置并在更改数据(操作一)后维护b数组,使b数组依然适用。
同时还要开一个struct(用于a数组)记录一个id(输入顺序)一个va(输入内容)。
因为要初始化(根据输入数据)b数组要把a sort一遍因为是sort结构体就要自定义cmp(重点来了!)因为我们要模拟稳定的排序所以自定义cmp中除了正常操作还有一点,如果a的输入顺序比b大也要交换。.
初始化b数组遍历一遍a数组将b[a[i].id]设为i(意为第a[i].id个数在排序后在i的位置)
接下来就是维护b数组的问题。
如果替换的数值比原来大就要向左边做一次冒泡,把它放到合适的位置。(如果它不交换了就break掉,能节省不少时间)如果替换的数值比原来的大就想做做冒泡……(同理)
在第一种操作结束之前,我们还要再初始化一遍b数组(初始化b数组遍历一遍a数组将b[a[i].id]设为i)。
如果是第二种操作,十分简单输入x,输出b[x]即可(别问我为什么,看了那么多还不明白就重看吧!)。
代码:
#include<bits/stdc++.h> using namespace std; struct s{ int id; int va; }a[8010]; int n,q,b[8010]={0}; int cmp(const s &a,const s &b) { if(a.va!=b.va) return a.va<b.va; else return a.id<b.id; } int main() { #ifdef LOCAL freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif cin>>n>>q; for(int i=1;i<=n;i++) { cin>>a[i].va; a[i].id=i; } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) { b[a[i].id]=i; } while(q--) { int t; scanf("%d",&t); if(t==1) { int x,v; scanf("%d%d",&x,&v); if(a[b[x]].va<v) { a[b[x]].va=v; for(int i=b[x];i<n;i++) { if(a[i].va>a[i+1].va||(a[i].va==a[i+1].va&&a[i].id>a[i+1].id)) swap(a[i],a[i+1]); else break; } } else { a[b[x]].va=v; for(int i=b[x]-1;i>=1;i--) { if(a[i].va>a[i+1].va||(a[i].va==a[i+1].va&&a[i].id>a[i+1].id)) swap(a[i],a[i+1]); else break; } } for(int i=1;i<=n;i++) { b[a[i].id]=i; } } else { int x; scanf("%d",&x); printf("%d\n",b[x]); } } return 0; }
最后,祝大家暑假快乐!
这篇关于插入排序(CSP-J 2021 T2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升