#105. 「USACO1.3」Ski Course Design 题解
题目传送门
欢迎大家指出错误并联系这个蒟蒻
更新日志
- 2023-02-01 17:20 文章完成
- 2023-02-03 16:09 文章审核通过
- 2023-02-04 22:15 修改了注释
- 2023-05-16 21:44 修改了 $\LaTeX$
- 2023-07-01 15:59 修改了代码
题目知识点
模拟+搜索+枚举
题意说明
$N$ 座山峰( $1\le N \le1000$ ),每座山都有一个在 $0$ 到 $100$ 之间的整数的海拔高度。如果滑雪训练营的最高和最低的山峰海拔高度差大于17就要收税。如果他改变山峰的高度(使最高与最低的山峰海拔高度差不超过 $17$ ),约翰可以避免支付税收。 (偷税漏税+愚公移山?)
如果改变一座山 $x$ 单位的高度成本是 $x^2$ 单位,求约翰最少需要付多少钱。
代码+解释
// #105. 「USACO1.3」Ski Course Design
// code by:st20250113
#include <bits/stdc++.h> //伟大的万能头文件
using namespace std;
int a[1005]; // 用来存山峰的高度
int n; // 共有n座山峰
int ans = 1e9; // 存大一点,以防万一
int main() {
cin >> n;
for (int i = 0; i < n; i++) { // 这步不用解释了,凡是学过数组的人都知道
cin >> a[i];
}
for (int low = 0; low + 17 <= 100; low++) { // low+17<=100指枚举山峰的最低高度,最低高度+17不能大于100
int high = low + 17; // 最高高度不用枚举,直接加17就可以了。因为要用到最高高度,所以前面最低高度+17必须小于等于100
int sum = 0; // sum用来存费用和。
for (int i = 0; i < n; i++) { // 记得还要枚举一遍a数组
if (a[i] < low) { // 如果太小时的情况
sum += (low - a[i]) * (low - a[i]); // 增加到最低高度,因为这样花费最少
}
if (a[i] > high) { // 如果太大时的情况
sum += (a[i] - high) * (a[i] - high); // 减少到最高高度,因为这样花费最少
}
}
if (sum < ans) { // 如果现在的花费比原先的最小花费还小
ans = sum; // 答案要的是最小花费,所以我们需要不断的更新
}
}
cout << ans << endl;
return 0; // 华丽结束
}
// QYC最帅