SRM600 Div2Easy TheShuttles
問題概要
会社でX人運べるシャトルバスを数台雇いたい。このシャトルバスを雇う費用は一台 baseCost + X * seatCost で計算される。各地点に住む従業員数が vector
解法
二重ループの全探索。
先ずX人を決め打ちするループを回す必要があるので、Xの取りうる範囲を考える。すると、シャトルバス一台について高々 vector
シャトルバス一台の料金が求まったので、次は全ての地点でかかる費用を計算するループを回す必要がある。空席が出ても全員を運ぶ必要があるので、一つの地点におけるシャトルバスの台数は ceil((double)cnt[i]/x) となる。
#define ALL(x) (x).begin(), (x).end() class TheShuttles { public: int getLeastCost(vector <int> cnt, int baseCost, int seatCost) { int const MXCNT = *max_element(ALL(cnt)); int const N = cnt.size(); int ans = INF; for(int x=1; x<=MXCNT; x++) { int sum = 0; int const aShuttle = baseCost + x * seatCost; for(int i=0; i<N; i++) { sum += ceil((double)cnt[i]/x)*aShuttle; } ans = min(ans, sum); } return ans; } };