SRM 624 Building Heights DivI 题解

和前面的题目差不多，具体看：http://community.topcoder.com/stat?c=problem_statement&pm=13211&rd=15857

思路：

1 排序

2 计算当前建筑物数为i的时候，所有可能的最小建筑物修改数

3 每次计算i+1的时候，所有可能的最小建筑物修改数

4 同时可以比较得到i+1的时候最小修改数

得到的程序也不复杂

#include <vector> #include <algorithm> #include <limits.h> #include <math.h> using namespace std;class BuildingHeights { public: int minimum(vector<int> heights) {int n = (int)heights.size();sort(heights.begin(), heights.end());vector<int> cost(n, 0);int ans = 0;for (int i = 0; i < n-1; i++){int c = INT_MAX;for (int j = n-1; j > i; j--){cost[j] = cost[j-1] + (heights[j]-heights[j-1])*(i+1);c = min(c, cost[j]);}ans ^= c;}return ans; } };

总结

以上是生活随笔为你收集整理的SRM 624 Building Heights DivI 题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。