记录编号	446985	评测结果	AAAAAAAAAA
题目名称	[Codeforces 819B] B先生和PR移位	最终得分	100
用户昵称	Arrow	是否通过	通过
代码语言	C++	运行时间	0.351 s
提交时间	2017-09-09 10:39:31	内存使用	11.76 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 1000010

	int n,cnt=0,s_b=0,s_s=0;
	long long sum=0;
	int p[MAXN]={0};
	int b[2*MAXN]={0}; // 分别表示 比自己序号大或小i的数的  个数

void work()
{ 
	long long cur=sum;
	for(int k=1;k<=n-1;k++)  //枚举 1~n-1种移位，分别计算由k-1种状态推出第k种状态的值
	{
		int end=p[n-k+1]; //第k-1种状态的末位，要特殊考虑
		if(end<n) //在上一状态中end比n小
			s_s--;
		if(end>n) //在上一状态中end比n大  
			s_b--,b[end-n+k-1]--; // 在某个状态中，end实际比其初始序号大end-n+k
		if(end==n)
			b[end-n+k-1]--;
		long long tmp=s_s-s_b+b[0+k-1]+abs(end-1)-abs(end-n);
		cur+=tmp;
		if(sum>cur)
			sum=cur,cnt=k;
		// 更新在k状态的各值
		s_s+=b[0+k-1],s_b-=b[1+k-1];
		if(end>1)
			s_b++,b[end-1+k]++;
		if(end==1)
			b[end-1+k]++;
	}
}

int main()
{
	freopen("MrBB1.in","r",stdin);
	freopen("MrBB1.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
		sum+=(long long)abs(p[i]-i);
		if(p[i]<i)
			s_s++;
		if(p[i]>i)
			b[p[i]-i]++,s_b++;
		if(p[i]==i)
			b[0]++;
	}
	work();
	cout<<sum;
	printf(" %d\n",cnt);
return 0;
}