Description:
n軒の家が道沿いに建っている。(n <= 2 <= 10万)
そして、各家庭について、足りないワイン/余ったワインをどれだけ買いたい/売りたいといった情報が与えられる。
1軒隣の家まで1本のワインを移動させるコストを1とした時に、全ての需給を満たす為にどれだけのコストが必要か?
需要と供給は丁度つり合っている。
Answer:
greedyに「一番右端の余っているワインを一番右端の欲しい人に移動させる」という操作を繰り返せば良い。
このワイン移動の割り当てがワインの経路同士が交差しない唯一の割り当てとなる。
Source: