题解：P13492 【MX-X14-T2】反转时光

前言：这道题目的数据真的很水。

进入正题：

一.我们怎么确定这道题是什么算法?

我们可以先看

100\%

的数据：

对于

100\%

的数据，

1 \le n \le 10^{5}

，保证

p

是一个

1 \sim n

的排列。

由此，我们可知暴力是会超时的，通过此题要用

O(n)

或

O(n \log n)

的做法，考虑数学或二分。但这道题不满足使用二分的单调性，所以这道题我们使用数学。

二.如何得出规律?

我们可以针对样例：

对于样例一的解释：这明显是一个连续上升的序列，不用交换，所以

k

为

1

。同样的，只要序列满足连续上升，则

k

为

1

。

对于样例二的解释：这个序列有两个依次上升的子序列，我们可以交换这两个子序列，使它变得有序，所以

k

的值为

2

。同样的，序列只要满足有两个依次上升的子序列，我们的

k

就等于

2

。（注：这两个序列一定是依次上升的，否则就不能输出

2

。）

对于样例三的解释：对于这个完全无序的序列，我们可以输出

3

，可以证明

3

是最小的

k

，我们只需要每次将最大值、次大值、次次大值......依次找出来，将它的左边变成序列一，本身变成序列二，右边变成序列三，将序列一和序列二交换，就可以将最大值、次大值、次次大值......依次放在序列的左边，也就是说，对于一个长度为

n

的完全无序的序列，最多进行

n

次操作，就可以将它变成一个有序的序列，以下是例子：

对于序列：

3

、

2

、

4

、

1

，我们可以很容易发现它是完全无序的，我们可以做出以下操作：

交换 $3$ 、 $2$ 和 $4$ 得序列 $4$ 、 $3$ 、 $2$ 、 $1$ 。
交换 $4$ 和 $3$ 得序列 $3$ 、 $4$ 、 $2$ 、 $1$ 。
交换 $3$ 、 $4$ 和 $2$ 得序列 $2$ 、 $3$ 、 $4$ 、 $1$ 。
交换 $2$ 、 $3$ 、 $4$ 和 $1$ 得序列 $1$ 、 $2$ 、 $3$ 、 $4$ 。

综上，我们的

k

最小是

3

。

三.代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],l;
bool check(int r){//判断 k 是否是 1 或 2。
	for(int i=r;i<n;i++){
		if(a[i]!=a[i+1]-1){
			return 0;
		}
	}
	for(int i=1;i<r-1;i++){
		if(a[i]!=a[i+1]-1){
			return 0;
		}
	}
  //以上是遍历序列，看看它是否满足样例二的格式。
	return 1;//满足返回 1。
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==1){
			l=i;//记录 1 的位置，遍历的时候有一个起始点。
		}
	}
	if(check(l)&&l==1){//特判，如果它是样例一的格式，输出 1。
		cout<<1;
	}
	else if(check(l)){//否则如果它满足有两个依次上升的子序列，输出 2。
		cout<<2;
	}
	else{//如果它是完全无序的序列，输出 3。
		cout<<3;
	}
	return 0;
}

题解：P13492 【MX-X14-T2】反转时光

文章操作

进入正题：

一.我们怎么确定这道题是什么算法?

二.如何得出规律?

三.代码

相关推荐

评论

题解：P13492 【MX-X14-T2】反转时光