比赛 CSP2023-J模拟赛 评测结果 AAAAAAAAAAAAAAAAAWAA
题目名称 排列变换 最终得分 95
用户昵称 心灵震荡 运行时间 0.506 s
代码语言 C++ 内存使用 6.08 MiB
提交时间 2023-10-18 20:12:38
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int n, p[N], s[N], cur, ans, cnt;
bool flag1 = 1;

int main()
{
	freopen("permutrans.in", "r", stdin);
	freopen("permutrans.out", "w", stdout);
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> p[i], flag1 &= (p[i] == i);
	if(flag1) cout << n << ' ' << 0;
	else
	{
		for(int i = 1; i <= n; i++)
		{
			if(p[i] != n)
			{
				s[max(0, p[i] - i + 1)]++;
				s[max(0, n + p[i] - i + 1)]++;
			}
		}
		cur = ans = n - s[0], cnt = 0;
		for(int i = 1; i < n; i++)
		{
			cur = cur + (p[n - i + 1] != n) - s[i];
			if(ans < cur) ans = cur, cnt = i;
		}
		cout << ans << ' ' << cnt;
	}
	return 0;
}

/*
1 6 2 5 4 3 7 -> 4
7 1 6 2 5 4 3 -> 3 (4 - 1)
3 7 1 6 2 5 4 -> 3 (3 - 1 + 1)
4 3 7 1 6 2 5 -> 4 (3 + 1)
5 4 3 7 1 6 2 -> 5 (4 + 1)
2 5 4 3 7 1 6 -> 4 (5 - 2 + 1)
6 2 5 4 3 7 1 -> 5 (4 - 1)
*/