[cf] 746 div2 B. Hemose Shopping

前言

t a g : tag : tag:限制交换 数学分析 排序 *1200 逆向思维 传送门 :

题意 : 给定你一个数组和一个限制 x x x,询问是否可以通过有限次操作使得数组变为非降序

操作 : 选择任意两个下标 i , j i,j i,j当且仅当 ∣ i − j ∣ > = x |i-j|>=x ∣i−j∣>=x的时候才可以进行交换

思路 :

本题还可以使用数学归纳法进行证明分析,奈何数学不好

我们对原数组进行一次复制,然后将复制数组进行排序

显然排序后的数组 和 原数组 不相同的地方都是需要进行交换的

我们可以反过来进行思考,考虑不能交换的位置, 即 i + x > n ∣ ∣ i − x < 1 i+x>n||i-xn∣∣i−x>n>>x; for(int i = 1;i>a[i]; b[i] = a[i]; } sort(b+1,b+1+n); for(int i = 1;i n && i - x