Codeforces #175 Div2 C "Building Permutation"
問題
http://www.codeforces.com/problemset/problem/285/C
訳
Codeforces Round #175 Div2 - くじらにっき++で訳してくれています。
考えた事
例えば n=4でa[]={ 4, -2, 0, 2 }だったら、
aをソートして{ -2, 0, 2, 4 }
それを { 1, 2, 3, 4 }にすれば最小なんじゃないかなぁ
(紙に書いて試す)
なんかうまい事補正してくれてダイジョブそう
事後
「既に1..nの範囲にある要素はそのままにして…」という記述があったらしいですね。
これに気付いていたら(いや気付けよ)律儀に守ってしまっていたかも。
ソースコード
/* 比較関数 */ int comp( const void *c1, const void *c2 ) { int tmp1 = *(int *)c1; int tmp2 = *(int *)c2; if( tmp1 < tmp2 ) return -1; if( tmp1 > tmp2 ) return 1; return 0; } int arr[300001]; int main() { istream& in = cin; int n; in >> n; for( int i = 1; i <= n; i++ ){ in >> arr[i]; } qsort( arr+1, n, sizeof(int), comp ); long long res = 0; for( int i = 1; i <= n; i++ ){ res = res + abs( i - arr[i] ); } cout << res << endl; }