题目链接：点击查看
题目大意：给出一个长度为 n 的排列 p，可以执行数次循环右移的操作，问的最小值是多少
题目分析：暴力的话用 n * n 很容易实现 ，但数据是 1e6 的，显然又不能用暴力去写，所以考虑优化
首先去掉绝对值后将 n 个数分成两类：
p[ i ] <= ip[ i ] > i
假设第一类有 upper 个，第二类有 lower 个，那么循环右移一次，不难看出其变化的贡献是 delta = upper - lower，由此我们可以实时维护 upper 和 lower 的个数，就可以快速更新每次循环右移后的答案了
更具体的来说，我们第 i 次循环右移，实质上是将第 n - i + 1 个数字放到了第一个位置，因为这个位置比较特殊，所以每次需要单独计算贡献，而不能利用 upper 和 lower 进行计算
需要观察到，随着循环右移次数的增加，第二类数也会变成第一类数，而第一类数当且仅当从最后一个位置放到第一个位置时才会变换
考虑第二类数何时会变成第一类数，因为每次循环右移一次，假设 p[ i ] 不变，但其相对下标会加一，所以在 p[ i ] - i 次循环右移后，p[ i ] 会回到下标为 p[ i ] 的位置，此时 lower--，upper++
所以模拟就好了，记得数组开大点
代码：
//#pragma GCC optimize(2)//#pragma GCC optimize("Ofast","inline","-ffast-math")//#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include<iostream>#include<cstdio>#include<string>#include<ctime>#include<cmath>#include<cstring>#include<algorithm>#include<stack>#include<climits>#include<queue>#include<map>#include<set>#include<sstream>#include<cassert>#include<bitset>using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e6+100;int a[N],shift[N];int main(){#ifndef ONLINE_JUDGE// freopen("data.ans.txt","r",stdin);// freopen("data.out.txt","w",stdout);#endif// ios::sync_with_stdio(false);int n,lower=0;LL sum=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",a+i);if(a[i]>i){shift[a[i]-i]++;lower++;}sum+=abs(a[i]-i);}LL mmin=sum,mark=0;for(int i=1;i<n;i++)//枚举转移了多少次 {int x=a[n-i+1];sum+=(n-lower-1)-lower+abs(x-1)-abs(x-n);lower-=shift[i];if(x>1){lower++;shift[x-1+i]++;}if(sum<mmin){mmin=sum;mark=i;}}printf("%lld %lld\n",mmin,mark);return 0;}
