読者です 読者をやめる 読者になる 読者になる

SRM600 Div2Easy TheShuttles

問題概要
会社でX人運べるシャトルバスを数台雇いたい。このシャトルバスを雇う費用は一台 baseCost + X * seatCost で計算される。各地点に住む従業員数が vector cnt で与えられるので、すべての従業員を運ぶようにしたとき会社の負担する費用の合計を最小化せよ。

解法
二重ループの全探索。
先ずX人を決め打ちするループを回す必要があるので、Xの取りうる範囲を考える。すると、シャトルバス一台について高々 vector cnt の最大値まで座席があれば十分と分かるので、これがXの最大値である。また座席数Xの最小値は1であり、cntの最小値ではないことに注意。
シャトルバス一台の料金が求まったので、次は全ての地点でかかる費用を計算するループを回す必要がある。空席が出ても全員を運ぶ必要があるので、一つの地点におけるシャトルバスの台数は 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;
  }
};