USACO备考冲刺必刷题 | P3650 Ski Course Design

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO备考冲刺必刷题 | 汇总-CSDN博客

【题目描述】

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

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

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

【输入】

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

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

【输出】

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

【输入样例】

5
20
4
1
24
21

【输出样例】

18

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, a[1005], minn=1e9;
int main()
{cin >> n;  // 输入nfor (int i=1; i<=n; i++) {  // 输入所有山峰高度cin >> a[i];}sort(a+1, a+n+1);  // 按照从大到小排序for (int i=0; i<=83; i++) {  // 遍历山峰的最小高度（最高高度就是i+17）int sum = 0;  // 定义每轮总金额，初始为0for (int j=1; j<=n; j++) {  // 遍历所有山峰if (a[j]<i) {  // 小于最小高度，就增加两者之差需要的成本sum += (i-a[j])*(i-a[j]);} else if (a[j]>i+17) {  // 高于最大高度，也增加两者之差需要的成本sum += (a[j]-i-17)*(a[j]-i-17);}}minn = min(minn, sum);  // 每轮统计后计算最小值}cout << minn << endl;  // 输出最小值return 0;
}

【运行结果】

5
20
4
1
24
21
18