기로에 서다

문제 www.acmicpc.net/problem/20300 20300번: 서강근육맨 PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다. www.acmicpc.net 풀이 구해야 하는 건 기구를 두 개씩 사용해서 일어나는 근손실의 합의 최대를 M이라 할 때, 이를 최소화해야 합니다. "최대의 최소화" 꼴이라 이분 탐색도 가능하지만 그보다 간단하게 근손실의 정도를 오름차순으로 정렬하고, 매칭 되지 않은 오른쪽 끝 값(최대 값)을 왼쪽 끝 값(최소 값)과 매칭시켜주는 방법을 통해 해결할 수 있습니다. (n이 홀 수일 경우에 한 번은 1개의 기구만 선택해야 하므로 이는 최대 값을 선택한 후, ..