AcWing 1353. 寒假每日一题活动---day17滑雪场设计(枚举+贪心)P25
原题链接
简单
作者:
初静
,
2021-03-07 10:21:43
,
所有人可见
,
阅读 240
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int h[N];
//最终所有点只在一个区间内。 [i, i + 17]
int main () {
scanf("%d", &n);
for (int i = 0; i < n; i ++) scanf("%d", h[i]); //debug这里没加&会出现 Segmentation Fault
int res = 1e8; //定义一个最大值,对于每个山峰来说最大值是100,代价是10000,共1000个高度,最大cost为1e7,写成1e8就够了
for (int i = 0; i + 17 <= 100; i ++) { //枚举所有区间[0,17],[1,18],[...],[83,100]
int cost = 0;
int l = i, r = i + 17;
for (int j = 0; j < n; j ++) { //所有的山峰修改的代价之和
if (h[j] < l) cost += (l - h[j]) * (l - h[j]);
if (h[j] > r) cost += (h[j] - r) * (h[j] - r);
}
res = min(res, cost);
}
cout << res << endl;
return 0;
}