切換
舊版
前往
大廳
主題

ZeroJudge - a941: 10041 - Vito's large family 解題心得

Not In My Back Yard | 2019-04-11 22:18:05 | 巴幣 2 | 人氣 272

題目連結:


題目大意:
這題基本上一樣,但是親戚數量 r 的範圍改為 0 < r < 2, 000, 000。


範例輸入:
3
2 2 4
3 2 4 6
4 2 1 999 5


範例輸出:
2 2
4 4
1001 2


解題思維:
可以看到 Vito 會在的位置為親戚的門號號碼之中位數。因此我們需要找到中位數(方法見三天前的文章)。

找到之後,就單純地算距離即可。但是因為門號號碼介於 0 ~ 30000 之間,因此可以統計親戚門號號碼為 0 的有多少、 1 的有多少……然後,算距離時就是絕對值乘上有幾個親戚是當前這個門牌號碼。如此可以省下一點時間(因為不必跑過所有親戚的位置)。

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

創作回應

更多創作