相关链接
题目传送门:http://codeforces.com/contest/819/problem/B
解题报告
这题是今年SCOI D2T1的一部分
具体的做法就是如果$i$变成$i+1$,那么有多少$|p_i – i|$会增加和减少
对于每个$|p_i – i|$,“从增加变到减少 或 从减少变到增加” 只会进行一次
于是总的时间复杂度就是:$O(n)$的
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1000009; int n, p[N], chg[N], delta[2]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } int main() { n = read(); LL cur = 0, ans, pos = 0; for (int i = 1; i <= n; i++) { p[i] = read(); cur += abs(p[i] - i); delta[p[i] > i]++; if (p[i] > i) { ++chg[p[i] - i]; } else { ++chg[n - i + p[i]]; } --chg[n - i + 1]; } ans = cur; for (int i = 1; i < n; i++) { cur += delta[0] - delta[1]; cur += abs(p[n - i + 1] - 1) - abs(p[n - i + 1] - n - 1); if (cur < ans) { ans = cur; pos = i; } delta[1] -= chg[i]; delta[0] += chg[i]; } cout<<ans<<' '<<pos<<endl; return 0; }