TopCoder SRM624 BuildingHeightEasy 题解

本题题意就是求有一组建筑物，问把这些建筑物的M个都统一到同一高度。须要的最小改动高度是多少？

题意隐含的意思就是由于是建筑物，所以不能降低，仅仅能添加了。

本题能够使用暴力搜索，由于数据量少。

可是事实上能够小排序。然后再求高度差的。

排序之后从第M个建筑物開始搜索。第M个建筑物与前面M个建筑物组成的建筑物群肯定是当前最小改动高度了。

一个题目要求的类和一个測试程序:

#include <vector>
#include <algorithm>
#include <limits.h>
#include <math.h>
using namespace std;

class BuildingHeightsEasy
{
public:
	int minimum(int M, vector<int> &heights)
	{
		sort(heights.begin(), heights.end());
		int ans = INT_MAX;
		for (int i = M-1; i < (int)heights.size(); i++)
		{
			int tmp = 0;
			for (int j = i-M+1; j < i; j++) //j = M-i-1竟然写成这种错误
			{
				tmp += heights[i] - heights[j];
			}
			ans = min(ans, tmp);
		}
		return ans;
	}
};

void BuildingHeightsEasy_run()
{
	int m, n;	
	scanf("%d %d", &m, &n);
	vector<int> heights(n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &heights[i]);
	}
	BuildingHeightsEasy build;
	printf("%d
", build.minimum(m, heights));
}