题目描述

题目的要求是最高峰和最小的山峰的差值不可以大于17，也就是说任意两个山峰的 高度都是小于等于17的

结论与证明

山峰的初始高度位于0-100，修改后的山峰的高度一定位于0-100之间
从理论上来看是因为山峰的高度小于0好像也没有办法实现啊。。。
证明：
题目的本质含义就是说对于给定的n个点，找到一个区间为最优区间，所有的点都落在区间上符出的代价最小
该区间的最大最小值之差不可以大于17

如果每一次从最大值最小值入手的话，修改一次区间的最大值最小值就会发生变化，所以不可以直接判断最值
那么题目就只能转换成，把所有的点都映射到一个区间，这个区间使得符出的代价最小

package day;

import java.util.Scanner;

public class 滑雪场设计 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner =new Scanner(System.in);
        int n=scanner.nextInt();
        int a[]=new int [n];

        for(int i=0;i<n;i++){
            a[i]=scanner.nextInt();
        }

        int ma=Integer.MAX_VALUE;
        for(int st=0;st+17<=100;st++){
            int l=st;
            int r=st+17;
            int cost=0;
            for(int i=0;i<n;i++){
                if(a[i] < l ) cost+=(l-a[i])*(l-a[i]);
                else if (a[i] < r) {
                    cost+=(a[i]-r)*(a[i]-r);
                }
            }
            ma=Math.min(ma, cost);
        }
        System.out.println(ma);
    }

}