Balloons (UVa Live Archive North America - Southeast - 2010/2011)

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4863

問題

Nチームが参加しているコンテストが開催された。各チームに風船をK個配りたいのだが、部屋Aからの距離はDA、Bからの距離はDBとなっている。各部屋には風船がA個、B個ある時、最適な風船の配り方をした時の移動時間の合計を求めよ。
1<=N<=1000
0<=A,B<=10000
0<=DA,DB<=1000

解法

DA-DBでソートして制約を満たすようにしながらgreedyに風船を配っていく。