우체국
면접 대비시간 제한2초메모리 제한128 MB
수직선 위 마을들의 위치와 인구가 주어질 때, 전체 가중 거리 합을 최소화하는 지점을 찾고 동률이면 가장 작은 값을 출력합니다.
문제
수직선 위에 N개의 마을이 있다. i번째 마을은 좌표 X[i]에 있고, 그 마을에는 A[i]명이 산다.
이 마을들을 위해 우체국 하나를 세우려고 한다. 우체국의 위치는 모든 사람까지의 거리 합이 최소가 되도록 정한다. 우체국을 세울 위치를 출력하는 프로그램을 작성하라.
마을마다 한 번씩 거리를 더하는 것이 아니라, 각 마을의 인구수만큼 사람까지의 거리를 더한다는 점에 유의하라.
입력
첫째 줄에 N (1 <= N <= 100,000)이 주어진다. 다음 N개의 줄에는 각 마을의 위치 X[i]와 인구 A[i]가 한 줄에 하나씩 주어진다.
모든 입력은 정수이며, |X[i]| <= 1,000,000,000, 1 <= A[i] <= 1,000,000,000 이다.
출력
모든 사람까지의 거리 합이 최소가 되는 우체국의 위치를 첫째 줄에 출력한다. 가능한 위치가 여러 개이면 그중 가장 작은 위치를 출력한다.