题解:CF1455D Sequence and Swaps

· · 题解

CF1455D 题目传送门

题目大意

给定一个由 n 个整数组成的序列 a,以及一个整数 x。你的任务是使序列 a 有序。

你可以任意多次(包括零次)执行以下操作:选择一个整数 i,满足 1 \leq i \leq na_i > x,然后交换 a_ix 的值。

解决思路

首先来看一个例子,如果 a = [0, 2, 3, 5, 4], x = 1,则以下操作序列是可能的:\ 先选择 i = 2,然后 a = [0, 1, 3, 5, 4], x = 2;\ 再选择 i = 3,然后 a = [0, 1, 2, 5, 4], x = 3;\ 最后选择 i = 4,然后 a = [0, 1, 2, 3, 4], x = 5

若现在有 i < j,而且 a_{i} 需要交换但没有交换,则 a_j 也无法交换。

代码展示