主題

ZeroJudge - b855: 一封信 解題心得

Not In My Back Yard | 2021-02-09 00:00:01 | 巴幣 0 | 人氣 37

題目連結:


題目大意:
輸出第一列給定一正整數 T (T ≦ 10),代表有 T 筆測試資料。每筆第一列給定一正整數 N (N ≦ 1000),代表有 N 個數字。接著有 N 列輸入,每列給定一正整數 K (K ≦ 20000),代表每個數字之值。

小明現在對於每個數字 K 可以選擇他要往東走 K 單位的距離或是往北走 K 單位。試問,小明最後所在的地點距離最一開始(還沒有走任何一步前)出發的地點最近可以多近?請輸出該距離平方之值。



範例輸入:
1
3
1
4
7


範例輸出:
74


解題思維:
暴力窮舉每個數字應分配到北邊或東邊的這個方法是不可行的。

假設分配到北邊的數字之值總和為 a 、東邊總和為 b ,兩邊總和 a + b 為 L 。因此我們的所求為 a ^ 2 + b ^ 2 ,則根據算幾不等式:
(a ^ 2 + b ^ 2) ÷ 2 ≧ √(a ^ 2 × b ^ 2)
簡化後變為
a ^ 2 + b ^ 2 ≧ 2ab
上式等號發生於 a = b,此時 a ^ 2 + b ^ 2 為最小值。

但是因為原先湊成 a 與 b 的是給定的 N 個數字。所以不一定能剛好湊到 a = b,但是根據算幾不等式的意義,只要 a 盡量接近 b ,則算術平均數(這邊為 a ^ 2 + b ^ 2 即所求)就會盡量地小。

因此本題就變成給定 N 個數字,能湊到的、最接近 L ÷ 2 (L 為數字總和)之值為何,即經典的換硬幣問題之變型,如這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作