1. Vito's family (CPE10406, UVA10041) - CPE一顆星解答與說明
CPE一顆星49題解答 - pdf 電子檔,售價 199 元,
購買電子檔可將筆記與完整解答帶著走,
坐車、上課時皆可隨時複習,
不受網路或廣告影響,
若有需要請來信購買 greens2314@gmail.com
題目
- Vito 在紐約有非常多的親戚,他希望在紐約找到一間房子,這間房子到每個親戚家的距離總和,要是最少的距離
輸入說明
- 輸入資料包含很多筆測試資料
- 每筆測資,包含親戚數量與每位親戚家的街號
- 親戚數量介於1~499、街道範圍介於1~29999
- 多位親戚可住在同一條街
輸出說明
- 針對每筆測試資料,計算出 Vito 到每位親戚家的最短距離總和
- 街與街的距離 = 街道數字相減取絕對值
解題技巧
- 中位數
- 是指一組數字的中間數字;即是有一半數字的值大於中位數,而另一半數字的值小於中位數,其意義是在所有資料中居於中間位置的代表
- 排序
- 街道的數字同時代表距離,透過排序,可得知中位數
解題過程
取得輸入
- 取得資料筆數
- 根據資料筆數取得親戚數量
- 根據親戚數量取得街道編號
- 將街道編號存入陣列中
將親戚的街道位置由小至大排序
- 呼叫 Arrays 類別提供的 sort() 方法
- https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html
- 假設親戚有 5 位,分別住在:2、5、8、4、2街
- 排序後為:2 、2、4、5、8街
計算中位數
計算最小距離總和並印出
- 宣告 sum 變數,統計距離
- 使用 foreach 將各街道編號 減掉 中位數編號,取絕對值並進行家總
- 取絕對值要呼叫 Math.abs () 方法
- 奇數情況:
- 中位數有 1 個
- 假設親戚有 5 位 ,分別住在: 2 、2、4、5、8 街
- 中位數 4,Vito 住在 4 街,到其他親戚家的距離總和即是最小值 9
- 偶數情況:
- 中位數有 2 個,擇一即可
- 假設親戚有 4 位(偶數),分別住在: 2 、4、5、8街
- 中位數 4,Vito 住在 4 街,到其他親戚家的距離總和即是最小值 7
- 中位數 5,Vito 住在 5 街,到其他親戚家的距離總和即是最小值 7
留言
張貼留言