【acwing 寒假每日一题（入门组）】day17 滑雪场设计

题目来源：滑雪场设计

题目描述

农夫约翰的农场上有 N 个山峰，每座山的高度都是整数。

在冬天，约翰经常在这些山上举办滑雪训练营。

不幸的是，从明年开始，国家将实行一个关于滑雪场的新税法。

如果滑雪场的最高峰与最低峰的高度差大于17，国家就要收税。

为了避免纳税，约翰决定对这些山峰的高度进行修整。

已知，增加或减少一座山峰 x 单位的高度，需要花费 x2 的金钱。

约翰只愿意改变整数单位的高度，且每座山峰只能修改一次。

请问，约翰最少需要花费多少钱，才能够使得最高峰与最低峰的高度差不大于17。

输入格式
第一行包含整数 N。

接下来 N 行，每行包含一个整数，表示一座山的高度。

输出格式
输出一个整数，表示最少花费的金钱。

数据范围
1≤N≤1000,
数据保证，每座山的初始高度都在 0∼100 之间。

输入样例：

5
20
4
1
24
21

输出样例：

18

样例解释
最佳方案为，将高度为 1 的山峰，增加 3 个单位高度，将高度为 24 的山峰，减少 3 个单位高度。

思路

题目分析：

1. 最高峰与最低峰的高度差不大于17，每座山的高度都是整数，约翰只愿意改变整数单位的高度
   那么其实是让我们找一个区间端点是整数得区间，将所有山峰高度放置到这个区间即可
2. 数据保证，每座山的初始高度都在 0∼100 之间。
   区间大小是17，区间左端点最小是0，右端点最大是100，暴力枚举所有得区间即可

要点证明

为什么区间左端点最小是0，右端点最大是100呢？
假设最优解区间为[i, j],我们先解决前面半个问题。

1. 假设 i<0， 并且j<0 由于每座山的初始高度都在 0∼100 之间，最极端得情况下，我们将所有山峰得高端全部变为0，这个代价也更小，所以i<0， 并且j<0 是不可能得
2. 假设 i<0， 并且j>=0 由于每座山的初始高度都在 0∼100 之间，我们将所有需要小于0的山峰的高度都变为0，则区间变为[0, j]这个区间显然长度小于17，并且消耗的代价更小，所以i<0， 并且j>=0 是不可能得
3. 所以i>=0 并且j>=0
4. 后面的证明同理

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int n;
int h[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>h[i];
    
    int res=INT_MAX; //初始值
    for(int i=0;i+17<=100;i++) //枚举所有区间
    {
        int cost=0,l=i,r=i+17; //记录左右端点
        for(int j=0;j<n;j++) //枚举所有山峰高度放在这个区间内得花费
            if(h[j]<l) cost+=(h[j]-l)*(h[j]-l); //山峰高度在区间得左边
            else if(h[j]>r) cost+=(h[j]-r)*(h[j]-r);//山峰高度在区间得右边
        res=min(res,cost);//要求代价最小
    }
    cout<<res<<endl;
    return 0;
}