java滑雪,AcWing 1353. 滑雪场设计

java滑雪,AcWing 1353. 滑雪场设计

(暴力枚举)

读入所有山峰高度并排序

最优的最小山峰高度一定在[读入的最小山峰高度,读入的最大山峰高度 - 17]之间

依次假设[读入的最小山峰高度,读入的最大山峰高度 - 17]中的每一个高度为最优解对应的最小山峰高度

求出每个假设需要花费的金额，求出最小的花费

Java 代码

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.Collections;

public class Main {

public static void main(String[] args) throws IOException {

//读入所有山峰高度到一个Arraylist中

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.adLine());

ArrayList list = new ArrayList();

for (int i = 0; i < n; i++) {

list.add(Integer.adLine()));

}

//排序山峰高度

Collections.sort(list);

//ans用来存每次枚举的最小值，sum用来存每次枚举的花费

int ans = Integer.MAX_VALUE;

//依次假设[读入的最小山峰高度,读入的最大山峰高度 - 17]中的每一个高度为最优解对应的最小山峰高度

for (int i = (0); i <= (n - 1) - 17; i++) {

int sum = 0;

for (int num : list){

if (num < i) sum += (i - num) * (i - num);

if (num > (i + 17)) sum += (num - i - 17) * (num - i - 17);

}

ans = Math.min(ans, sum);

}

System.out.println(ans);

}

}