概要
何人かの従業員の送迎のため、シャトルバスを運行したい。バス停は N 箇所あって、i 番のバス停には cnt[ i ] 人の従業員がいる。シャトルバスを一台作るには baseCost の費用が掛かる。更に、座席数が X のとき X * seatCost の費用が上乗せされる。X は自由に選んで作ることができるが、全てのバスで同じにならなければならない。
シャトルバスの運行に於いては、一台のバスは高々一つのバス停にだけ従業員を迎えに行く。全ての従業員を迎えに行けるだけのバスを揃える際の必要コストの最小値を求めよ。
解法
X が決まったとき、c 人いるバス停に向かわせるバスの必要数は c を x で切り上げ整数除算した値、すなわち、( c + x - 1 ) / x 台のバスが必要です。各バス停について向かわせるバスの台数が分かったので、全てのバス停について台数を計算して、合計コストを求めることができます。
さて、解候補となる X は何通りあるでしょうか？ 最も多くの従業員がいるバス停に関して、そこにいる人数よりも大きい X を設定するのは無駄なので、解の上界は cnt の最大値ということになります。下界が 1 なので 100 通りしかありません。従って、X を全通り試すことができます。X を全て試し、最も安いコストを達成したときのコストを return すれば OK です。
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( v, c ) for ( auto &v : c ) class TheShuttles { public: int getLeastCost( vector <int> cnt, int baseCost, int seatCost ) { int res = INT_MAX; REP( x, 1, 101 ) { int tmp = 0; FOR( c, cnt ) { int num = ( c + x - 1 ) / x; tmp += num * ( baseCost + seatCost * x ); } res = min( res, tmp ); } return res; } };
