技術室奥プログラミングコンテスト#3 F - 天使とふすま
問題概要
1ヵ所に集まっているN個の襖を隙間も重複も無いように並べる。1個の襖を動かすには動かす距離をyとしてB[i]*y消費する。この時、条件を満たす並べ方にするまでの体力消費量の最小値を求める。
解法
2つの数値が1つの物に与えられているときはその2つの数値をどうにかしてsortするのが定石な気がするので頑張ってみる。すると、襖の並びは左からA[i]/B[i]の数値が大きい物ほど左にありそうという気持ちになるので、pair<double,pair<int,int>>で数値を管理してあげて、doubleの所にA[i]/B[i]を入れてあげてsortした後に愚直に計算してあげて、AC。sortがネックなのでO(NlogN)。
