AcWing 1353. 滑雪场设计（贪心）

AcWing 1353. 滑雪场设计（贪心）

【题目描述】
农夫约翰的农场上有 N N N个山峰，每座山的高度都是整数。
在冬天，约翰经常在这些山上举办滑雪训练营。
不幸的是，从明年开始，国家将实行一个关于滑雪场的新税法。
如果滑雪场的最高峰与最低峰的高度差大于 17 17 17，国家就要收税。
为了避免纳税，约翰决定对这些山峰的高度进行修整。
已知，增加或减少一座山峰 x x x单位的高度，需要花费 x 2 x^2 x2的金钱。
约翰只愿意改变整数单位的高度，且每座山峰只能修改一次。
请问，约翰最少需要花费多少钱，才能够使得最高峰与最低峰的高度差不大于 17 17 17。

【输入格式】
第一行包含整数 N N N。
接下来 N N N行，每行包含一个整数，表示一座山的高度。

【输出格式】
输出一个整数，表示最少花费的金钱。

【数据范围】
1 ≤ N ≤ 1000 1≤N≤1000 1≤N≤1000
数据保证，每座山的初始高度都在 0 ∼ 100 0sim 100 0∼100之间。

【输入样例】

5
20
4
1
24
21

【输出样例】

18

【样例解释】
最佳方案为，将高度为 1 1 1的山峰，增加 3 3 3个单位高度，将高度为 24 24 24的山峰，减少 3 3 3个单位高度。

【分析】

由于每座山的初始高度在 0 ∼ 100 0sim 100 0∼100之间，因此很容易证明最高峰和最低峰的高度一定也在 0 ∼ 100 0sim 100 0∼100这个范围内，也就是高度区间为 0 ∼ 17 , 1 ∼ 18 , … , 83 ∼ 100 0sim 17,1sim 18,dots ,83sim 100 0∼17,1∼18,…,83∼100中的其中一个。因此我们可以枚举每个区间 [ l , r ] [l,r] [l,r]，计算出将所有山峰的高度 h [ i ] h[i] h[i]修改到这个区间范围内需要的总开销 c o s t cost cost（若 h [ i ] < l h[i]<l h[i]<l则 c o s t + ( l − h [ i ] ) 2 cost+(l-h[i])^2 cost+(l−h[i])2；若 h [ i ] > r h[i]>r h[i]>r则 c o s t + ( h [ i ] − r ) 2 cost+(h[i]-r)^2 cost+(h[i]−r)2），取所有区间开销的最小值即可。

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;const int N = 1010;
int h[N];
int n;int main()
{cin >> n;for (int i = 0; i < n; i++) cin >> h[i];int res = 0x3f3f3f3f;for (int l = 0; l + 17 <= 100; l++){int r = l + 17, cost = 0;for (int i = 0; i < n; i++)if (h[i] < l) cost += pow(l - h[i], 2);else if (h[i] > r) cost += pow(h[i] - r, 2);res = min(res, cost);}cout << res << endl;return 0;
}