問題はこちら
No.693 square1001 and Permutation 2 - yukicoder
数列の順序は関係ないのでソートしてから考えて良い。
1から順に作ることを考えると、小さい方から順に使うのが最適であることがわかるので、Σ|a[i]-i|が解
#define swap(p,q)(p^=q^=p^=q) int a[99]; int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d",a+i); for(int i=0;i<n;i++)for(int j=1;j<n;j++)if(a[j-1]>a[j])swap(a[j-1],a[j]); int s=0; for(int i=0;i<n;i++)s+=abs(a[i]-(i+1)); printf("%d",s); }
バケツソートを使うかバブルソートを使うかは悩みどころだが、バケツソートの方が短くなりそうな気がしたのでそれで実装
バブルソートの方は試してない
これを
a[99]; n,t,s,i,k; int main(){ scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&t); a[t]++; } for(int i=0;i<n;i++){ while(a[k]==0)k++; s+=abs(k-(i+1)); --a[k]; } printf("%d",s); }
こうじゃ
a[99],i,s; main(k){ for(;~scanf("%d",a)?++a[*a]:a[k]--?s+=abs(k-++i),1:++k<60;); printf("%d",s-1); }
nもまとめて読み込んで、ループをn回ではなく十分大きな定数回実行している。このため答えが1ずれるので引いている。
入力の読み込みにa[0]を使うことで一時変数を削減している。(+1B-2Bで1B削減)
96B