[USACO1.3]Ski Course Design

# [USACO1.3]Ski Course Design

题目描述

农民约翰的农场里有 \(n\) 座山峰，每座山都有一个在 \(0\) 到 \(100\) 之间的整数的海拔高度。在冬天,因为山上有丰富的积雪，约翰经常开办滑雪训练营。

不幸的是，约翰刚刚得知税法在滑雪训练营方面有新变化，明年开始实施。在仔细阅读法律后，他发现如果滑雪训练营的最高和最低的山峰海拔高度差大于 \(17\) 就要收税。因此，如果他改变山峰的高度（使最高与最低的山峰海拔高度差不超过 \(17\) ），约翰可以避免支付税收。

如果改变一座山 \(x\) 单位的高度成本是 \(x^2\) 单位，约翰最少需要付多少钱才能使海拔最高的山峰与海拔最低的山峰的高度只差不超过 \(17\) 约翰只愿意改变整数单位的高度。

输入格式

输入的第一行是一个整数，代表山峰的数量 \(n\)。

第 \(2\) 行到\((n + 1)\) 行，每行一个整数。第 \(i\) 行的整数 \(a_i\) 代表第 \(i\) 座山的海拔高度。

输出格式

输出一行一个整数，代表约翰需要支付修改山海拔高度的总金额。

样例 #1

样例输入 #1

5
20
4
1
24
21

样例输出 #1

18

提示

样例输入输出 1 解释

约翰保持高度为 \(4\)、\(20\) 和 \(21\) 的山的高度。他增高高度为 \(1\) 的山，变成高度 \(4\) ，花费 \(3^2 = 9\)。他降低了高度为 \(24\) 的山变成高度 \(21\)，也花费 \(3 ^ 2 = 9\)。因此总共花费 \(9 + 9 = 18\)。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le n \le 1000\)，\(0 \leq a_i \leq 100\)。

Code

#include <bits/stdc++.h>
using namespace std;
int a[1010];
int main()
{
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	int ans=0xffffff;
	for(int low=1;low<=100;low++)
	{
		for(int high=low;high<=100;high++)
		{
			int sum=0;
			for(int i=1;i<=n;i++)
			{
				if(a[i]<low)
				{
					sum+=(low-a[i])*(low-a[i]);
				}
				else if(a[i]>high)
				{
					sum+=(a[i]-high)*(a[i]-high);
				}
			}
			if(sum<ans&&high-low<=17) ans=sum;
		}
	}
	cout << ans;
	return 0;
}