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

题目传送门

欢迎大家指出错误并联系这个蒟蒻

更新日志

2023-02-01 17:20 文章完成
2023-02-03 16:09 文章审核通过
2023-02-04 22:15 修改了注释

题目知识点

模拟+搜索+枚举

题意说明

$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最帅