58 C Trees

Codeforces

問題

長さnの数列a[i]が与えられる。
a[i]を、a[1]=a[n], a[2]=a[n-1], a[3]=a[n-2],……かつ、
a[2]=a[1]+1, a[3]=a[2]+1, ……を満たすように変えたい。


変更する項の数のを最小にするとき、変更する項の数を求めよ。

制約条件

  • 変更後の各項は自然数
  • n≦10^5
  • a[i]≦10^5

解法

初項を決めると数列は1通りに定まる。
初項がkであるような数列に一致する項の数をcnt[k]とする。


n-(cnt[k]の最大値)を求めれば、変更すべき項の数がわかる。

int n,a,cnt[100001];

void run(){
	cin>>n;
	memset(cnt,0,sizeof(cnt));
	rep(i,n){
		cin>>a;
		if(i<(n+1)/2)if(0<a-i&&a-i<100001)cnt[a-i]++;
		if(i>=(n+1)/2)if(0<a+i+1-n&&a+i+1-n<100001)cnt[a+i+1-n]++;
	}
	cout<<n-*max_element(cnt,cnt+100001)<<endl;
}