(暴力枚举)
本题错误的思路是使用贪心,用贪心会导致不断的增加/减少山的高度会让区间排序重新打乱
正确思路:
枚举所有可能的区间左端点i
让所有的山峰修改高度进入[i, i + 17]区间内
而花钱数最小的方案就是,让高度小于i的山的高度增高到i 这个区间左端点,让高度大于i的山的高度减少到i+17这个区间右端点
一个问题:为什么我们可以知道要让山峰的高度修改到0-100的区间
答:只有两端的山峰往中间靠拢,才有可能找到花费最小的方案
C++ 代码
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
int m[1005];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++) scanf("%d", &m[i]);
int ans = INF; //让答案初始化为一个很大的数
for(int i = 0; i <= 100 - 17; i++){ //枚举各个可能的区间左端点
int cost = 0;
for(int j = 0; j < n; j++){ //不断的将所有的山峰划入区间的左端点或者右端点
if(m[j] < i) cost += (i - m[j]) * (i - m[j]);
else if(m[j] > i + 17) cost += (m[j] - i - 17) * (m[j] - i - 17);
}
ans = min(cost, ans);
}
cout << ans << endl;
return 0;
}