i~i+17 表示在 0~100 中高度可能存在的区间 高度在 i~i+17 内的山峰一定是满足要求的 所以
接下来枚举对于每个 i~i+17 区间 枚举山峰
对于在 i~i+17 内的山峰 高度不变
对于在i 左侧的山峰,高度变为i
对于在 i+17 右侧的山峰,高度变为 i+17;;
最后使山峰高度都处于 i~i+17 内 计算对于i~i+17 内:所有山峰在此区间内的最小花费达到局部最优解
局部最优->全局最优
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1010;
int L[N];
int main(){
cin>>n;
for(int i = 0;i < n ; i ++) cin >> L[i];
int res = 1e8;
for(int i = 0;i+17<=100;i++){//枚举差值为17的区间
int cost = 0,l = i,r = i + 17;
for(int j = 0;j < n;j ++){//枚举每座山峰
if(L[j] < l) cost += (l-L[j])*(l-L[j]);
else if(L[j] > r) cost += (L[j] - r)*(L[j] - r);
}
res = min(res,cost);
}
cout<<res;
return 0;
}