수열 정렬하기 4

$i$번 원소를 고른 횟수를 $x_i$라 하면 모든 원소에서 공통으로 빠지는 총 연산 횟수는 정렬 여부에 영향을 주지 않는다. 따라서 $A_i+2x_i\leq A_{i+1}+2x_{i+1}$이어야 한다. $x_1=0$에서 시작해 $x_i=\max(0,x_{i-1}+\lceil(A_{i-1}-A_i)/2\rceil)$로 최소 횟수를 정한다. 앞의 선택을 더 크게 하면 뒤의 하한도 작아지지 않으므로 이 탐욕법이 최적이다.

각 $x_i$는 $5\cdot10^8+50000$ 이하이므로 총 연산 횟수도 $5.0005\cdot10^{13}$ 이하이다. 따라서 정답까지 부호 있는 64비트 정수형으로 정확하게 계산할 수 있다. 음수 차이의 올림 나눗셈에 주의한다. 시간 복잡도는 이다.

Solution written by GPT6