区间枚举
时间复杂度:$O(84 \times n)$
因为 $N$ 的取值范围只有 $1000$ 且每座山的高度在 $0 \le h \le 100$ 之间,故直接区间枚举即可。
区间枚举的范围
因为每座山的高度在 0 - 100 之间,则只需枚举
[0, 17] [1, 18] [2, 19] [3, 20], ... , [83, 100]
当在区间范围之外时,找离区间最近的边界计算费用即可,取某一区间的最小费用即可。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, INF = 1e9;
int n;
int h[N];
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> h[i];
}
// 区间枚举, 保证 <= 17 即可
// [0, 17]
// [1, 18]
// [2, 19]
// [83, 100]
int mn = INF;
for (int low = 0; low <= 83; ++low) {
int high = low + 17;
int cost = 0;
for (int i = 0; i < n; ++i) {
if (h[i] > high) cost += (h[i] - high) * (h[i] - high);
if (h[i] < low) cost += (low - h[i]) * (low - h[i]);
}
mn = min(mn, cost);
}
cout << mn << endl;
return 0;
}