棋盤挑戰

題目來源：USACO 2014 January Contest Bronze
時間限制：\(1000ms\) 記憶體限制：\(64mb\)

題目描述

農夫約翰的農場上有 \(N\) 個山丘，每座山的高度都是整數，
在冬天，約翰經常在這些山上舉辦滑雪訓練營，
不幸的是，從明年開始，國家將實行一個關于滑雪場的新稅法，
如果滑雪場的最高峰與最低峰的高度差大于17，國家就要收稅，
為了避免納稅，約翰決定對這些山峰的高度進行修整，
已知，增加或減少一座山峰 \(x\) 單位的高度，需要花費 \(x^2\) 的金錢，
約翰 只愿意改變整數單位 的高度，
請問，約翰最少需要花費多少錢，才能夠使得最高峰與最低峰的高度差不大于17，

輸入格式

第一行包含整數 \(N\) ，
接下來 \(N\) 行，每行包含一個整數，表示一座山的高度，

輸出格式

輸出一個整數，表示最少花費的金錢，

資料范圍

\(1 ≤ N ≤ 1000\)
資料保證，每座山的初始高度都在 \(0～100\) 之間，

樣例輸入

樣例輸出

樣例解釋

最佳方案為，將高度為 \(1\) 的山峰，增加 \(3\) 個單位高度，將高度為 \(24\) 的山峰，減少 \(3\) 個單位高度，

解題思路：列舉

拿到給定的山高度的陣列之后，
因為每座山的初始高度都在 \(0～100\) 之間，
所以設定一個山的最小標準 \(i\) ，從 \(0\) 開始，到 \(100-17\) 之間，也就是 \(i \in [0,83)\) ，
將 \(i\) 設定為一個最小標準，所有山比最小標準矮的，進行增高，
將 \(i+17\) 設定為最大標準，所有山比最大標準高的，將其變矮，

列舉所有情況，取花費最小的一項，即得題解，

解題代碼-Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] mountains = new int[n];
        for (int i = 0; i < n; i++) {
            mountains[i] = input.nextInt();
        }
        input.close();
        int ans = Integer.MAX_VALUE;  //給答案賦一個很大的初始值
        for (int i = 0; i < 100 - 17; i++) {  //以 [i,i+17] 為山的高度區間，列舉所有可能
            int w = 0;
            for (int j = 0; j < n; j++) {
                if (mountains[j] < i) {  //若山的高度不在區間內，則計算需要花費的金錢
                    w += Math.pow(mountains[j] - i, 2);
                } else if (mountains[j] > i + 17) {
                    w += Math.pow(mountains[j] - i - 17, 2);
                }
            }
            ans = Math.min(ans, w);  //列舉所有的情況，取花費金錢最小的值作為答案，
        }
        System.out.println(ans);
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252515.html

標籤：其他

上一篇：PAT Advanced 1012 The Best Rank

下一篇：Java List分批處理

2021寒假每日一題《滑雪場設計》