【AGC001F】Wide Swap

令\(i\)的位置为\(Q_i\):

从这个角度考虑问题和给定的操作,就是每次交换相邻的两个数,并且它们要满足差不小于\(k\),使得最终\(1\)的位置尽量靠前,然后\(2\)的位置尽量靠前,依此类推。

可以发现差小于\(k\)的数的相对位置不会发生变化,并且满足这个条件的排列都是合法排列。

另外可以证明的是最小字典序的\(Q\)一定对应最小字典序的\(P\)。求出最小字典序后在\(i\)前面的数一定都是比\(i\)小或者比\(i\)大且差小于\(k\)且在原来\(Q\)中就在\(i\)前面的数。这样就保证了\(i\)在不比它小的数中尽可能靠前,就得到了最小字典序的\(P\)。

那么如果\(|i-j|<k\)并且\(P_i<P_j\)那么从\(i\)向\(j\)连边,求这张图的最小字典序拓扑排列即可。

边数\(O(n^2)\),考虑优化。每个点只需要连向左右最小的满足条件的数即可,其它的边实际上不需要。

说点什么

您将是第一位评论人!

提醒
wpDiscuz