問題はこちら
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