[CSP-J2021]插入排序题解

SSER_ZRQ · 2021-10-23 21:59:08 · 题解

插入排序题解

要点

• 题目贴代码：一般题目贴代码都是没安好心，需要多个心眼
• 看数据范围：n=8000, q=2e5,推测时间复杂度O(n^2)

  做法

1. 按照题目给的步骤去做，O(n^2*q), 裂开。即使用快排，归并，复杂度也不理想。
2. 想一想发现没有必要排序，只需求a[x]是第几小，则用O(n)查找,总的时间复杂度O(nq)，预计分数76

76分代码：https://www.luogu.com.cn/paste/gu6y3wwi

3. • 优化：发现每一次改动a[x]的值只会让a[1...x-1]与a[x+1...n]的位置+1或-1。
   • 而对于 a[x] 的位置，只需循环一遍查找它新的位置即可。
   • 先用O(n^2)求出原来每一个数的位置，当op==1时用O(n)修改每个数当前的位置，当op==2用O(1)输出。
   • 总时间复杂度 O(n^2+(op==1)情况*n+(op==2)情况）。题目说的“修改次数<=5000”也肯定了此算法。预计分数100。
   • （如果文字看不明白，可看代码。）

AC代码：https://www.luogu.com.cn/paste/uoa8zglc

格式应该还行吧