RiseOJ – 짝짓기

설명

농부 존은 소들이 곁에 정신적 지지가 되어 줄 다른 소가 있을 때 젖을 짜기가 더 쉽다는 것을 알게 되었다. 그래서 그는 $$M$$ 마리의 소 ( $M \leq 1,000,000,000$ , $$M$$ 은 짝수)를 $$M/2$$ 개의 쌍으로 나누려 한다. 각 소 쌍은 젖 짜기를 위해 헛간의 별도 축사로 안내된다. 이 $$M/2$$ 개 축사에서의 젖 짜기는 동시에 진행된다.

문제를 조금 복잡하게 만드는 점은, 농부 존의 소들이 저마다 다른 우유 생산량을 갖는다는 것이다. 우유 생산량이 $$A$$ 와 $$B$$ 인 소가 짝지어지면, 둘의 젖을 모두 짜는 데 총 $$A+B$$ 단위의 시간이 걸린다.

농부 존이 소들을 최선의 방법으로 짝지었을 때, 전체 젖 짜기 과정을 완료하는 데 걸리는 최소 시간을 구하도록 도와주자.

문제 출처: Brian Dean

제약

문제 출처: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ 이 주어진다 ( $1 \leq N \leq 100,000$ ). 다음 $$N$$ 개의 줄에는 두 정수 $$x$$ 와 $$y$$ 가 주어지며, 이는 FJ에게 우유 생산량이 각각 $$y$$ 인 소가 $$x$$ 마리 있음을 나타낸다 ( $1 \leq y \leq 1,000,000,000$ ). $$x$$ 들의 합이 전체 소의 수 $$M$$ 이다.

출력 형식

소들이 최적으로 짝지어졌을 때, FJ의 소들의 젖을 모두 짜는 데 걸리는 최소 시간을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 pairup.in · 출력을 쓸 파일 pairup.out

예제 1

입력

출력

설명

Here, if the cows with outputs 8+2 are paired up, and those with outputs 5+5 are
paired up, the both stalls take 10 units of time for milking. Since milking
takes place simultaneously, the entire process would therefore complete after 10
units of time. Any other pairing would be sub-optimal, resulting in a stall taking more than 10
units of time to milk.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > US Open > Silver

올림피아드 > USACO > 2016-2017 > US Open > Silver

태그

JudgeUSACO

짝짓기

평가 및 의견

풀이 제출