滑雪场修整(贪心、枚举)
n个整数在[0,100]之间,要使其最大值与最小值的差不大于17,可以将数字增大或减小,数字在原来基础上变化了x(整数)的大小,需要花费x^2,求最小花费。
输入样例:
5
20
4
1
24
21
输出样例:
18
样例解释:
最佳方案为,将1增加3个单位,将24减少3个单位。
思路:可以证明结果集中的每个数字都大于等于0且小于等于100,且数字的变化均为整数,则结果集的区间范围是[0,17]、[1,18]…[83,100],枚举每个区间,并在区间内枚举每个数字计算花费,最终取到最小。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int n, h[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> h[i];
int res = 1e9;
for(int i = 0; i + 17 <= 100; i++) //每个区间
{
int l = i, r = i + 17;
int cost = 0;
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;
}