题解：CF454B Little Pony and Sort by Shift

题目描述

题目传送门

给定一个长度为 $n$ 的数组 $a$，每次可以将最后一个元素移动到第一个，问：至少需要几次操作，让序列从小到大排好序，若无解输出 $-1$。

算法1

(暴力枚举)

不难想到，将最后一个元素拼接在第一个元素之前，就可以实现将链转换成环，再依次遍历在数组 $a_i$ 中长度为 $n$ 的子串（可以想象成在数组 $a$ 中有一个长度为 $n$ 会滑动的窗口），再检验是否满足题目要求就可以了。

时间复杂度 $O(n^3)$

C++ 代码

请读者自行实现

算法2

经过我不断摸索(看了一眼题解)，发现将最后一个元素移到最前边，实际上就是为了将满足 $$a_{i-1} > a_i$$ 的两个元素分离，成为合法的序列，但是如果有两组以上这样的元素，就无法满足题目要求了。

时间复杂度 $O(n)$

C++ 代码

#include <iostream>
using namespace std;

const int N = 100010;
int n;
int a[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	a[0] = a[n];
	
	int cnt = 0, ans = -1;
	for (int i = 0; i <= n; i++)
		if (a[i-1] > a[i]) { // 统计逆序对
			cnt++;
			ans = n - i + 1;
		}
	ans %= n; // 如果ans > n，肯定也可以用ans % n来满足题目要求
	cout << (cnt > 1 ? -1 : ans) << endl;
	
	return 0;
}