题目描述
农夫约翰的农场上有 N 个山丘,每座山的高度都是整数。
在冬天,约翰经常在这些山上举办滑雪训练营。
不幸的是,从明年开始,国家将实行一个关于滑雪场的新税法。
如果滑雪场的最高峰与最低峰的高度差大于17,国家就要收税。
为了避免纳税,约翰决定对这些山峰的高度进行修整。
已知,增加或减少一座山峰 x 单位的高度,需要花费 x² 的金钱。
约翰只愿意改变整数单位的高度。
请问,约翰最少需要花费多少钱,才能够使得最高峰与最低峰的高度差不大于17。
输入格式
第一行包含整数 N。
接下来 N 行,每行包含一个整数,表示一座山的高度。
输出格式
输出一个整数,表示最少花费的金钱。
数据范围
1≤N≤1000,
数据保证,每座山的初始高度都在 0∼100 之间。
输入样例:
5
20 4 1 24 21
输出样例:
18
样例解释
最佳方案为,将高度为 1 的山峰,增加 3 个单位高度,将高度为 24 的山峰,减少 3 个单位高度。
分析
- 在最优解中 所有高度都在[0,100]的范围内
- 所以我们只需要枚举范围内所有可能的区间
- 如果高度在区间范围内 则无代价
- 如果高度在区间范围的左边 则最小代价是到区间左边界的距离的平方
- 如果高度在区间范围的右边 则最小代价是到区间右边界的距离的平方
- 最后取每次枚举后各个高度的代价和中最小的一个代价和则为最小代价
代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[1010];
int main()
{
int i,n;cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int minn=1e8;
for(i=0;i+17<=100;i++){
int s=0;
for(int j=1;j<=n;j++){
if(a[j]<i) s+=(a[j]-i)*(a[j]-i);
else if(a[j]>i+17) s+=(a[j]-i-17)*(a[j]-i-17);
}
minn=min(minn,s);
}
cout<<minn;