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

SRM624 Div1Easy BuildingHeights

解法
ソートして累積和とった上で全探索。O(N^2)
元の配列に番号付けがされているが、全ての番号の数だけ最小のフロアを集めるので番号付けに意味がなく、いきなりソートして良い。

#include <bits/stdc++.h>
using namespace std;
#define INF (1<<28)
class BuildingHeights {
public:
  int minimum( vector <int> heights ) {
    int N = heights.size();
    sort(heights.begin(), heights.end());
    
    vector<int> sum(N+1);
    for(int i=0; i<N; i++) {
      sum[i+1] = sum[i] + heights[i];
    }
    
    vector<int> mini(N+1, INF);
    for(int i=0; i<N; i++)
      for(int j=i+1; j<N+1; j++)
	mini[j-i] = min(mini[j-i], heights[j-1]*(j-i) - (sum[j] - sum[i]));
    
    int ans = mini[1];
    for(int i=2; i<=N; i++)
      ans ^= mini[i];
    
    return ans;
  }
};