1353. 滑雪场设计

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

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

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

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

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

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

约翰只愿意改变整数单位的高度。

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

输入格式

第一行包含整数 N。

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

输出格式

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

数据范围

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

思路：
直接枚举最低山的高度即可，然后前后记录需要增加的高度，可以加个二分找到第一个比最高山的高度大的然后向后扫描记录 ，并更新答案

代码

import java.util.*;

public class Main {

    public static void main(String[] args) {

        int n;
        int []a=new int [1005];
        Scanner sc=new Scanner(System.in);

        n=sc.nextInt();
        for(int i=0;i<n;i++) {
            a[i]=sc.nextInt();
        }
        Arrays.sort(a,0,n);

        int ans=0x3f3f3f3f;
        int x;
        int sum;
        //枚举最低山的高度
        for(int i=0;i<=100;i++) {
            x=i;
            sum=0;
            for(int j=0;j<n;j++) {
                if(a[j]<i)sum+=(a[j]-x)*(a[j]-x);
                else break;
            }
            x=i+17;
            for(int j=n-1;j>=0;j--) {
                if(a[j]>x) sum+=(a[j]-x)*(a[j]-x);
                else break;
            }
            ans=Math.min(ans,sum);
        }
        System.out.println(ans);
    }
}