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に風船を配っていく。