등수 매기기
시간 제한2초메모리 제한256 MB
N명의 학생에게 1부터 N까지의 등수를 중복 없이 배정해 예상 등수와의 절대값 차이 합을 최소화하는 문제입니다.
문제
어느 프로그래밍 경시대회에 N명의 학생이 참가했다. 대회 전에 각 학생은 자신이 N명 중 몇 등을 할 것인지 예상 등수를 적어 제출했다.
실제 등수는 1등부터 N등까지 중복 없이 하나씩 배정해야 한다. 어떤 학생의 예상 등수가 A등이고 실제 등수가 B등이면, 이 학생의 불만도는 |A - B|이다.
모든 학생의 예상 등수가 주어졌을 때, 불만도의 총합이 최소가 되도록 실제 등수를 정하고 그 최소값을 출력하라.
입력
첫째 줄에 자연수 N이 주어진다. (1 <= N <= 500,000)
둘째 줄부터 N개의 줄에는 각 학생의 예상 등수가 하나씩 주어진다. 예상 등수는 500,000 이하의 자연수이다.
출력
불만도의 총합으로 가능한 최소값을 출력한다.