ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - e536: 10487 - Closest Sums　解題心得

Not In My Back Yard | 2019-11-18 17:29:57 | 巴幣 2 | 人氣 252
題目連結：
題目大意：
輸入有多筆測試資料。每筆測資第一列給定一正整數 n （1 ≦ n ≦ 1000，n ＝ 0 時代表輸入結束），代表有一含有 n 個元素的集合。接著有 n 列輸入，每列給定一整數，代表該集合中的元素內容。

接著給定一正整數 m （0 ＜ m ＜ 25），代表有 m 筆詢問。每筆詢問佔一列並給定一整數，代表要查詢的整數值。請對每個要查詢的數字找到：集合內兩兩總和的值，哪個總和之值最接近欲搜尋的數字。輸出格式請參見範例輸出。

範例輸入：
5
3
12
17
33
34
3
1
51
30
3
1
2
3
3
1
2
3
3
1
2
3
3
4
5
6
0
範例輸出：
Case 1:
Closest sum to 1 is 15.
Closest sum to 51 is 51.
Closest sum to 30 is 29.
Case 2:
Closest sum to 1 is 3.
Closest sum to 2 is 3.
Closest sum to 3 is 3.
Case 3:
Closest sum to 4 is 4.
Closest sum to 5 is 5.
Closest sum to 6 is 5.
解題思維：
首先將 n 個數倆倆的總和值全部求出來，放到一個陣列裡存起來。接著將該陣列由小到大（由大到小也可以）排序。

再來，就是對每個數字用二分搜尋法（Binary Search）去找該數字位於陣列的何處附近。然後作一些額外判斷該數字離哪個總和值比較近，就輸出何者。

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

作者相關創作

更多創作