제독 작전

• 시작점을 결정하면 제독 순서가 결정된다. 시작점이 왼쪽 끝이나 오른쪽 끝이어야만 최적이 될수 있다는 것은 쉽게 파악할수 있다.
  • 원래 대회에 처음 출제되었을때에는 조건이 조금 달랐다. 한쪽 끝에서 다른쪽 끝으로 이동하면서 순서대로 방문하는 것을 의도하고 낸 문제였지만, 당시의 문제에는 '시작할 위치에서 가까운 순서대로 제독해야 한다'라는 조건이 없었다. 대회가 끝나고 며칠 지나서, 일부러 오염 지점을 건너뛰고 이동했다가 다시 돌아오면서 제독하는게 최적인 반례가 제기되었고, 그 이후에 현재와 같이 문제가 수정되었다.
• 왼쪽 끝점에서 시작해서 오른쪽 끝점으로 이동할때와 오른쪽 끝점에서 시작해서 왼쪽 끝점으로 이동할때를 각각 계산해서 최소값을 찾으면 된다. 왼쪽에서 오른쪽으로 이동하는 경우만 설명하자
• 단순하게는 그냥 점들을 다 정렬해놓고 시뮬레이션을 돌리면 된다. 1개 점을 스킵하고 이동할 수 있으므로, 이것은 DP 방식으로 계산해도 된다. 정렬에 O(nlogn), dp계산에는 O(n)이 걸린다.
• 하지만, 그리디한 방법으로 접근할수도 있다. 맨 오른쪽 끝점의 위치를 x_n 이라고 하자. x_i 점에 제독제를 주고 나면, 제독하는데에 p_i가 들고 누수량이 1이 늘어난 채로 (x_n - x_i)의 거리를 이동해야 한다. 바꿔서 생각하면 각 x_i점에 제독제를 주는 행위는, 총 필요량을 p_i +(x_n - x_i) 만큼 늘리게 되는 것이다. 그래서 모든 곳에 제독제를 투여하게 되면, 제독제는 모두 ∑(p_i + x_n - x_i) 이 필요하게 된다. 이중에서 한 곳을 제외시켜서 필요한 제독제 양을 최소화시키려면 (p_i + x_n - x_i)가 가장 큰 x_i 를 제외시켜야 한다. 식을 정리하면 필요한 제독제의 양은 ∑(p_i + x_n - x_i) - max(p_i + x_n - x_i) = ∑p_i - ∑x_i + (n-1)*x_n - max(p_i - x_i) 이 된다. 이렇게 식을 정리하면, 정렬조차도 필요 없고, x_n (=max(x_i)), ∑p_i, ∑x_i, min(p_i - x_i)만 알면 되므로 그냥 O(n)에 계산이 가능하다
• 여기에서 주의해야 할 경우는, 가장 우측의 점 x_n을 제외시키게 되는 경우이다. 이때는 이동 거리가 우측에서 두번째 점까지로 바뀌게 되므로 식이 달라진다. 식으로 쓰면 ∑(p_i + x_{n-1} - x_i) - (p_n + x_{n-1} - x_n) 처럼 되는데.. 정리해보면 ∑p_i - ∑x_i + (n-1)*x_{n-1} - (p_n - x_n) 형태가 된다. 결국 우측에서 두번째 점, x_{n-1} 만 추가로 구하면 계산이 가능하고 시간복잡도는 여전히 O(n)이다
• 오른쪽에서 왼쪽으로 이동하는 경우에도 비슷하게 그리디한 접근을 취해서 최솟값을 구할수 있으므로, 왼쪽→오른쪽, 오른쪽→왼쪽 중에서 최솟값을 출력하면 끝

"""Solution code for "BOJ 31410. 제독 작전".

- Problem link: https://www.acmicpc.net/problem/31410
- Solution link: http://www.teferi.net/ps/problems/boj/31410

Tags: [greedy]
"""

import heapq
import sys


def main():
    N = int(sys.stdin.readline())
    x_and_p = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    x, p = zip(*x_and_p)
    sum_x, sum_p = sum(x), sum(p)
    max1, max2 = heapq.nlargest(2, x)
    min1, min2 = heapq.nsmallest(2, x)
    answer = min(
        sum_p - sum_x - max(pi - xi for xi, pi in zip(x, p)) + max1 * (N - 1),
        sum_p - sum_x - (p[x.index(max1)] - max1) + max2 * (N - 1),
        sum_p + sum_x - max(pi + xi for xi, pi in zip(x, p)) - min1 * (N - 1),
        sum_p + sum_x - (p[x.index(min1)] + min1) - min2 * (N - 1),
    )
    print(answer)


if __name__ == '__main__':
    main()