【学校题解】#105. 「USACO1.3」Ski Course Design 题解（2023-08-18更新）

szhiy / 2023-08-18 / 原文

#105. 「USACO1.3」Ski Course Design 题解

本文章的访问次数为次。

Part 1 提示

题目传送门
欢迎大家指出错误并私信这个蒟蒻
欢迎大家在下方评论区写出自己的疑问（记得 @ 这个蒟蒻）
本文已同步至学校网站、博客园。

Part 2 背景

这是这个蒟蒻的第三篇题解，也是这个蒟蒻对自己的 \(250\) AC 的纪念。
当然，这篇题解也不完全是自愿要写的，我也不会告诉你这是 \(qyc\) 要求的。

Part 3 更新日志

2023-02-01 17:20 文章完成
2023-02-01 17:20 文章同步至学校网站
2023-02-02 17:58 提交审核
2023-02-03 16:09 文章审核通过
2023-02-04 22:15 修改了注释
2023-05-16 21:44 修改了 \(\LaTeX\)
2023-07-01 15:59 修改了代码
2023-08-18 19:27 更改了文章格式，使文章看起来更加美观
2023-08-18 19:28 文章同步至博客园

Part 4 题目知识点

模拟+搜索+枚举

Part 5 题意说明

\(N\) 座山峰（\(1\le N \le1000\)）,每座山都有一个在 \(0\) 到 \(100\) 之间的整数的海拔高度。如果滑雪训练营的最高和最低的山峰海拔高度差大于 \(17\) 就要收税。如果他改变山峰的高度（使最高与最低的山峰海拔高度差不超过 \(17\)），约翰可以避免支付税收。 ~~（偷税漏税+愚公移山？）~~
如果改变一座山 \(x\) 单位的高度成本是 \(x^2\) 单位，求约翰最少需要付多少钱。

Part 6 代码

// #105. 「USACO1.3」Ski Course Design
// code by:st20250113
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a[1005];   // 用来存山峰的高度
    int n;         // 共有n座山峰
    int ans = 1e9; // 存大一点，以防万一
    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;
}