滑雪场设计

---

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

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

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

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

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

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

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

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

输入格式

第一行包含整数 N。

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

输出格式

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

数据范围

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

输入样例：

5
20
4
1
24
21

输出样例：

18

样例解释

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

---

其实这一题的话，如果你想不到用枚举来做的话，是很难想的。因为这一题，你进行将最小的加上去之后，可能他就不是最小的了，最大的减去之后，他有可能就不是最大的了。可能会有新的两座山峰不满足情况，也就是说，这一题中的两座山峰是动态变化的，所以想要通过找最大和最小来做的方法基本就GG了。

那我们怎么做呢？我们要学着在动中找变，正好我们观察一下数据，每座山峰的高度在1~100之间。

我们可以进行枚举修剪后最矮山峰的高度low , low显然是在1-83以内，然后让超过的山峰满足在17以内，低于low的山峰，修改到low，依次来计算一下费用。然后比较一下，输出最小费就行了。

#include 

using namespace std ;

const int N = 1010 ; 

int a[N] ; 

int main()
{
    int n ; 
    cin >> n ; 
    
    for(int i = 1 ; i <= n  ; ++ i)
    {
        cin >> a[i] ; 
    }
    
    //枚举一下 low
    int res = 1e9 ; 
    for(int low = 1 ; low <= 83 ; ++ low)
    {
        int fee = 0  ;
        for(int i = 1 ; i <= n ; ++ i)
        { 
            if(a[i] < low)
            {
                fee += pow(low - a[i] , 2) ; 
            }
            if(a[i] > low + 17)
            {
                fee  += pow(a[i] - low - 17 , 2) ;  
            }
        }
        res = min (fee , res) ; 
    }
    cout << res << endl ; 
    return  0 ; 
}

有时候当一个思路受阻的时候，要学着换一种思路，不要一条根本不通的路想要走到黑，只是浪费时间而已。