比赛 |
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)
*/