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; } };