原题链接
思路
本题如果以贪心的思路来理解,则会遇到如果根据贪心算法变更后的最高峰和最低峰会发生改变,产生后效性,导致贪心算法无效,再考虑到本题目数据量不大,山峰数量在1k以内,山峰高度在100之内,正所谓暴力出奇迹,可以使用枚举的方法对每个山峰高度进行枚举,从而得到最小的花费。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int main()
{
int res = 0x3f3f3f;//求最小值,则初始化为最大值
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
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 += (a[j] - l) * (a[j] - l);//当前山峰高于我的期望高度l
else if(a[j] > r) cost += (r - a[j]) * (r - a[j]);//当前山峰低于我的期望高度r
}
res = min(cost, res);
}
cout<<res<<endl;
return 0;
}