#B4171. [BCSP-X 2024 6 月小学高年级组] 选择排序
[BCSP-X 2024 6 月小学高年级组] 选择排序
题目描述
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每趟找出第 小的元素(也就是 中最小的元素),然后将这个元素与数组第 个位置上的元素 交换;在 趟之后序列 变为升序。
例如 :
- 第 1 趟交换 ,序列变为 ;
- 第 2 趟交换 ,序列变为 ;
- 第 3 趟交换 ,序列不变;
- 第 4 趟交换 ,序列变为 ;
现在给定初始序列 (保证 是排列,即 每个数恰好出现一次)和 个询问 (保证 ),请你依次输出第 趟之后的序列 。
输入格式
第一行 2 个整数 。
第二行 个整数 ,保证 是排列。
第三行 个整数 ,保证 。
输出格式
输出 行,第 行包含 个整数代表第 趟之后的序列 。
5 4
3 4 1 5 2
1 2 3 4
1 4 3 5 2
1 2 3 5 4
1 2 3 5 4
1 2 3 4 5
6 3
6 4 2 3 1 5
1 3 5
1 4 2 3 6 5
1 2 3 4 6 5
1 2 3 4 5 6
提示
对于所有数据,满足 $1 \leq n \leq 10^5, 1 \leq m \leq 10, 1 \leq A[i] \leq n, 1 \leq q[i] < q[i + 1] < n$,保证 是排列。
- 对于测试点 1~8:;
- 对于测试点 9~13:;
- 对于测试点 14~20:;