#B. 选择排序

    传统题 1000ms 256MiB

选择排序

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每趟找出第 ii 小的元素(也就是 𝐴[𝑖𝑛𝐴[𝑖 ∼ 𝑛] 中最小的元素,若有多个,选择最靠前的),然后将这个元素与数组第 ii 个位置上的元素 𝐴[𝑖]𝐴[𝑖] 交换;在 𝑛1𝑛 − 1 趟之后序列 AA 变为升序。

例如 𝐴=[3,4,1,5,2]:𝐴 = [3,4,1,5,2]:

  • 11 趟交换 𝐴[1],𝐴[3]𝐴[1], 𝐴[3],序列变为 [1,4,3,5,2] [1,4,3,5,2]
  • 22 趟交换 𝐴[2],𝐴[5]𝐴[2], 𝐴[5],序列变为 [1,2,3,5,4][1,2,3,5,4]
  • 33 趟交换 𝐴[3],𝐴[3]𝐴[3], 𝐴[3],序列不变;
  • 44 趟交换 𝐴[4],𝐴[5𝐴[4], 𝐴[5],序列变为 [1,2,3,4,5][1,2,3,4,5]

现在给定初始序列 𝐴[1𝑛]𝐴[1 \sim 𝑛] mm 个询问 𝑞[1,2,,𝑚]𝑞[1,2, \dots, 𝑚] 。请你依次输出第 𝑞[𝑖]𝑞[𝑖] 趟之后的序列 𝐴𝐴

输入描述

第一行有 22 个正整数 𝑛,𝑚𝑛, 𝑚。 第二行有 𝑛𝑛 个正整数 𝐴[1𝑛]𝐴[1 ∼ 𝑛],保证序列 𝐴𝐴 是排列,即 1n1 \sim n 每个数恰好出现一次。 第三行有 𝑚𝑚 个正整数 𝑞[1𝑚]𝑞[1 ∼ 𝑚],保证序列 qq 单调递增,即对 1i<m1 \leq i < m , 有 q[i]<q[i+1]q[i] < q[i+1]

输出描述

输出 mm 行,第 𝑖𝑖 行包含 𝑛𝑛 个整数,代表第 𝑞[𝑖]𝑞[𝑖] 趟之后的序列 𝐴𝐴

输入样例1

5 4
3 4 1 5 2
1 2 3 4

输出样例1

1 4 3 5 2
1 2 3 5 4
1 2 3 5 4
1 2 3 4 5

输入样例2

6 3
6 4 2 3 1 5
1 3 5

输出样例2

1 4 2 3 6 5
1 2 3 4 6 5
1 2 3 4 5 6

数据范围

测试点编号 nn\leq
181 \sim 8 1010
9139 \sim 13 20002000
142014 \sim 20 10510^5

对于所有测试点:1n1051 \leq n \leq 10^5, 1m101\leq m \leq 10, 1A[i]n1 \leq A[i] \leq n, 1q[i]<q[i+1]n1 \leq q[i] < q[i+1] \leq n

卉图编程奥赛部CSP-J 第二轮模拟赛

未参加
状态
已结束
规则
OI
题目
5
开始于
2024-7-29 14:00
结束于
2024-7-29 17:30
持续时间
3.5 小时
主持人
参赛人数
35