AcWing 1353. 滑雪场设计
原题链接
简单
作者:
xihb183
,
2024-01-14 08:15:13
,
所有人可见
,
阅读 33
/*
这个问题可以用不同的方法来解决。
一个简单的想法当然是蛮力 - 尝试所有可能的高度并找到最小值。
我们可以尝试所有可能的值,如下所示:
尝试修改海拔区间 (0,17)然后 (1,18), (2,19), ..., (83,100)。
对于每个海拔区间 (i,i+17),我们需要计算每个山丘 j 的成本:
如果山 j 的高程,比如山 [j],在区间 (i,i+17) 内,则没有成本。
如果它小于 i 则成本增加 (i-hill[j])^2
如果它大于 i+17 则成本增加 (hill[j]-(i+17))^2
该迭代的总成本将是修改所有山丘的成本之和。
对于每次迭代,扫描所有山高程需要 O(N) 时间。
由于我们尝试了所有可能的间隔,因此总时间为 O(NM),其中 M 是海拔范围的大小。
由于 N=1000 和 M=100 非常小,因此这种蛮力方法就足够了。
*/
#include<bits/stdc++.h>
using namespace std;
int get_cost(const vector<int> &hills, int high) {
int cost = 0;
for (int h : hills) {
int x;
if (h < high)
x = h - high;
else if (h > high + 17)
x = (high + 17) - h;
else
x = 0;
cost += x * x;
}
return cost;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> hills(n);
for (int &x:hills)
cin >> x;
int min_cost = INT_MAX;
for (int i = 0; i <= 100 - 17; i++)//穷举每一种情况
{
int cost = get_cost(hills, i);
min_cost = min(min_cost, cost);
}
cout << min_cost << endl;
return 0;
}