ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - e541: 10474 - Where is the marble　解題心得

Not In My Back Yard | 2019-11-25 12:43:59 | 巴幣 0 | 人氣 281
題目連結(jié)：
題目大意：
給定兩正整數(shù) N 、 Q （N、Q ≦ 10000，當(dāng) N ＝ Q ＝ 0 時(shí)代表輸入結(jié)束），代表接著有 N 列輸入以及 Q 筆的詢問。

接著的 N 列每列給定一非負(fù)整數(shù)（不超過 10000），代表一個(gè)數(shù)列的內(nèi)容。請(qǐng)將其排序後編號(hào)為 1 ～ N 。

再接著有 Q 列輸入，每列也給一非負(fù)整數(shù)（同樣也不超過 10000）。求此數(shù)有無在給定的數(shù)列之中。有的話，請(qǐng)輸出該數(shù)所在的編號(hào)位置；反之，請(qǐng)輸出該數(shù)字「not found」。輸出格式請(qǐng)參見範(fàn)例輸出。

範(fàn)例輸入：
4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0
範(fàn)例輸出：
CASE# 1:
5 found at 4
CASE# 2:
2 not found
3 found at 3
解題思維：
題目就要求排序了，而且編號(hào)是依據(jù)排序後編的，而非排序前。因此不用額外多存新的資訊，只要存數(shù)值即可。

排完序後，對(duì)於每筆的詢問就用二分搜尋法（Binary Search）去找數(shù)字即可。有找到就輸出找到的位置；反之就輸出「not found」。

此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。

創(chuàng)作回應(yīng)

更多創(chuàng)作