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

SRM 624 Div2 Medium BuildingHeightsEasy

問題

SRM 624 - TopCoder Wiki

色々な高さの建物がある時に,同じ高さの建物が最低M個出来るように 建物の高さを増設したい. 増設しなくてはいけない高さの最低の数を求める問題.

解答

増加だけしか出来ないので,既存の建物の何れかの高さに合わせるようにする. 各々の高さを選んだ時のコストを計算し,最適値を返す.

class BuildingHeightsEasy
{
public:
  int minimum(int M, vector <int> heights)
    {
      int n = heights.size();
      sort(heights.begin(), heights.end());
      int i, j;
      int res = INT_MAX;
      for (i = M-1; i < n; i++) {
        int cost = 0;
        for (j = 0; j < M; j++) {
          cost += heights[i] - heights[i-j];
        }
        res = min(res, cost);
      }
      return res;
    }
};