证明
1:首先取值范围都是在0~100之间的,山的高度只能在0-100之间取
2:如果给出了一堆山峰,之间的差距<=17,说明不需要整改
3:但是如果给出的两个山峰,1,24,之间的差距大于17,我们就需要整改,整改的话只能让1一定向右移动,24向左移动,不能说向外移动,那么之间的距离只会越来越大,所以整改后的区间也一定是在0~100之间的
在举一个极端的例子,一座山是0,一座山是100,我们只能让0变大,和100变小,不能让0变小,或者100变大,那么就相当于把一座山挖了个坑,另一座山变成了珠穆朗玛峰,之间的差距只会越来越大
所以说 整改后的区间也一定是在0~100之间的
4:然后我们就枚举100中的每一个17,也就是0-17,1-18,…,83-100,然后让小于左边界的向右移动,大于右边界的向左移动,在区间中的就不需要移动了,比较每一个17中移动所花费的代价,算出最小的内一个,就是我们想要的答案
在举例:本题中的1和24,他们之间花费代价最小的区间是4~21这个区间,无非就是让1向右移动了三个距离,24向左移动了3个距离,然后所有的山的高度都在4~21这个区间内了
Java代码
import java.util.Scanner;
public class Main{
static int N = 1010;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[N];
for(int i = 0; i < n; i ++) a[i] = in.nextInt();
int res = 0x3f3f3f3f; //res表示最少花费
for(int l = 0; l <= 100 - 17; l ++) //枚举84个区间
{
int money = 0; //每种方案的总花费
for(int i = 0; i < n; i ++)
{
if(a[i] < l) money += (a[i] - l) * (a[i] - l);
else if(a[i] > l + 17) money += (a[i] - l - 17) * (a[i] - l - 17);
}
res = Math.min(res,money);
}
System.out.print(res);
}
}
这个证明好评!