526互联

Educational Codeforces Round 109 (Rated for Div. 2) B. Permutation Sort

发布时间 2023-10-10 16:27:41作者: zsxuan

给一个长为 \(n\) 的排列 \(a\)，你可以执行以下操作：选择一个子数组并且按任意顺序重排，但这个子数组不能是数组本身。

询问最少经过多少次操作可以使得排列 \(a\) 变为升序。

定义操作次数为 \(ans\) 。

  • 若数组已经有序，\(ans = 0\) 。
  • 若 \(a_1 = 1\) 或者 \(a_n = n\)，只需要操作 \([2, n]\) 或者 \([1, n - 1]\) 一段即可， \(ans = 1\) 。
  • 若 \(a_1 = n\) 并且 \(a_n = 1\) ，通过两次操作使 \(a_1 = 1\) 或 \(a_n = n\) ，再经过一次操作即可。\(ans = 3\) 。(这一步容易忽略)
  • 否则通过一次操作使 \(a_1 = 1\) 或 \(a_n = n\) ，再经过一次操作即可。\(ans = 2\) 。
view 
#include <bits/stdc++.h>
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void solve(){
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	if (std::is_sorted(a.begin() + 1, a.end())) std::cout << 0 << '\n';
	else if (a[1] == 1 || a[n] == n) std::cout << 1 << '\n';
	else if (a[1] == n && a[n] == 1) std::cout << 3 << '\n';
	else std::cout << 2 << '\n';
}             
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}