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

SRM624 Div2Med BuildingHeightsEasy

解法
ソートして区間[i, i+M)を足したものをすべて調べる。heights[i+M-1]*M との差分が最小のとき、その差分を出力するだけ。

#include <bits/stdc++.h>
using namespace std;
#define allof(x) (x).begin(), (x).end()
class BuildingHeightsEasy {
public:
  int minimum(int M, vector <int> H) {
    sort(allof(H));
    int ans = INT_MAX;
    for(int i=0; i<H.size(); i++) {
      if(i+M-1>=H.size()) continue;
      int sum = accumulate(H.begin()+i, H.begin()+i+M, 0);
      if(M*H[i+M-1]-sum < ans) {
        ans = M*H[i+M-1]-sum;
      }
    }
    return ans;
  }
};