👉 CPE 一顆星選集列表(49題) 題目說明與解答
題目
- Vito 在紐約有非常多的親戚，他希望在紐約找到一間房子，這間房子到每個親戚家的距離總和，要是最少的距離
輸入說明
- 輸入資料包含很多筆測試資料
- 每筆測資，包含親戚數量與每位親戚家的街號
- 親戚數量介於1~499、街道範圍介於1~29999
- 多位親戚可住在同一條街
輸出說明
- 針對每筆測試資料，計算出 Vito 到每位親戚家的最短距離總和
- 街與街的距離 = 街道數字相減取絕對值
解題技巧
- 中位數
- 是指一組數字的中間數字；即是有一半數字的值大於中位數，而另一半數字的值小於中位數，其意義是在所有資料中居於中間位置的代表
- 排序
解題過程
取得輸入
- 取得資料筆數
- 根據資料筆數取得親戚數量
- 根據親戚數量取得街道編號
- 將街道編號存入陣列中
將親戚的街道位置由小至大排序
- 呼叫 Arrays 類別提供的 sort() 方法
計算中位數
- 中位數在陣列中的索引 = 親戚數量 / 2
- 假設親戚有 5 位(奇數) ，分別住在：2、5、8、4、2街
- 排序後為：2 、2、4、5、8街，其中 4 為中位數，中位數有 1 個
- 5位親戚 / 2 = 2.5，取整數，陣列索引 2 的位置，儲存的是第 4 街
- 假設親戚有 4位(偶數)，分別住在：2、5、8、4街
- 排序後為：2 、4、5、8街，其中 4 或 5 為中位數，中位數有 2 個，擇一即可
- 4位親戚 / 2 = 2，陣列索引 2 的位置，儲存的是 5 街
計算最小距離總和並印出
- 宣告 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
留言
張貼留言