思路:类似滑动窗口,从 [0, 17] 滑到 [83, 100], 高度不够的补上,太高的削掉。一边划一边取最小代价。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int h[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> h[i];
int res = 1e8;
for (int i = 0; i <= 100 - 17; i ++ ) //i从0遍历到83
{
int cost = 0, l = i, r = i + 17; //l ∈ (0, 87), r ∈ (13, 100)
for (int j = 0; j < n; j ++ ) //遍历每座山峰,使其对齐窗口
if (h[j] < l) cost += (l - h[j]) * (l - h[j]);
else if (h[j] > r) cost += (h[j] - r) * (h[j] - r);
res = min(res, cost);
}
cout << res << endl;
return 0;
}