pstopia Notes for Problem Solving Contest

[Easy] MergersDivOne

Topcoder SRM 536 Div1

Problem

매 순간 revenue 가 제일 작은 두 회사를 골라 합치는 과정을 반복하는 것이 최적이다. 다른 어떤 전략을 취해도 위 전략보다 좋아질 수 없음을 보이면 된다. 적당한 계산을 거치면 증명할 수 있고 직관적으로도 와닿는 사실이다.