分析
-
本题限制了山峰只能改变整数单位的高度,这保证了此题划分出的区间是有限的
-
山峰修剪后的高度必然在0~100以内
【简单证一下】不妨设修建后的山峰高度小于0(如在区间[-1~16]),因为我们输入保证了山峰的初始高度在0~100内,则若将那些被修剪为负值的山峰如果改成只修建到高度为0,那么一是这些山峰仍然在长度为17的区间内,二是修到0一定比修到负值花费更少,所以山峰修剪后的高度必然不会出现小于0的值。(同理可证伪大于100的情况)
所以,所有的山峰修剪过后,它们的高度都在不超过17的区间内,由于本题数据中山峰高度为0~100,所以我们可以枚举所有可能的区间,让修剪后的山峰高度在这个区间内,并计算这样修剪的总花费,对花费取最小值,就是我们的答案
高度范围为0~100,故我们可以划分出100-17+1=84个区间,分别为
【0,17】【1,18】【2,19】......【83,100】
以区间【50,67】来举例,将所有高度小于50山峰修剪为50,将所有高度大于67的山峰修剪为67,并计算花费
复杂度
划分的区间个数和高度范围同级别,即100; 每次需要枚举所有山峰,以将他们的高度修建到区间内,山峰数量是1000; 故大概是10万的复杂度,出解时间也就几十ms
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,a[N];
int main(){
cin >> n;
for(int i = 0;i < n; i++) cin >> a[i];
int res = 1e9;
for(int i = 0; i + 17 <= 100; i ++)
{
int cost = 0, l = i, r = i + 17;
for(int j = 0; j < n; j ++)
{
if(a[j] < l) cost += (l - a[j])*(l - a[j]);
if(a[j] > r) cost += (r - a[j])*(r - a[j]);
}
res = min(res, cost);
}
cout << res << endl;
return 0;
}