前言
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
