題目連結:
題目大意:
與
這題基本上一樣,但是親戚數量 r 的範圍改為 0 < r < 2, 000, 000。
可以看到 Vito 會在的位置為親戚的門號號碼之中位數。因此我們需要找到中位數(方法見
三天前的文章)。
找到之後,就單純地算距離即可。但是因為門號號碼介於 0 ~ 30000 之間,因此可以統計親戚門號號碼為 0 的有多少、 1 的有多少……然後,算距離時就是絕對值乘上有幾個親戚是當前這個門牌號碼。如此可以省下一點時間(因為不必跑過所有親戚的位置)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。