Codeforces #175 Div2. C. Building Permutation

さてここからが本番…と言いたいけど、今回はBとCの正解者数がほぼ同じだな…。
http://codeforces.com/contest/285/problem/C

問題

長さNの整数値配列が与えられる。
この配列に１回処理を行うと、いずれかの要素を+1または-1できる。
この配列をPermutationにするために必要な最少処理数を答える。

解法

配列中の数値が小さい順に1,2,3...,Nとなるように増減すればよいだけ。
処理量はソートがO(N logN)の最大か。

int N;
pair<ll,int> A[1000001];

void solve() {
	int f,r,i,j,k,l,x,y,cur,tar;
	
	N=GETi();
	FOR(i,N) A[i]=make_pair(GETi(),i);
	
	sort(A,A+N);
	ll res=0;
	FOR(i,N) res += abs((i+1)-A[i].first);
	cout << res << endl;
	
	return;
}

まとめ

Div2とはいえCにしては簡単。