主題

ZeroJudge - e894: 第 M 小數　解題心得

Not In My Back Yard | 2020-03-03 19:03:07 | 巴幣 0 | 人氣 224

題目連結：

e894: 第 M 小數

題目大意：

輸入有多列，每列給定兩正整數 N 、 M （3 ≦ N 、 M ≦ 10000），代表有一個 N × N 的矩陣 A 。

而該陣列各個位置的值由行與列決定，其公式為

A[i][j] ＝ i ^ 2 ＋ j ^ 2 ＋（N － 10000） × i ＋ j 。

其中 i 、 j 依序代表第幾列、第幾行（行列從 0 開始數，數到 N － 1）。

請找出陣列中第 M 小的數字之值為何。

範例輸入：

5 10

5 25

範例輸出：

-29956

20

解題思維：

直接暴力硬做（時間複雜度 O(N ^ 2)）基本上是會超時的。

所以可以採取一種作法：二分搜尋法（Binary Search）套進另一個二分搜尋法。

第一個二分（外圈的）用來二分答案（要輸出的值，假設該數字為 Q）、第二個二分（內圈）用來統計是否存在陣列裡至少有 M － 1 個數字小過 Q （代表 Q 至少第 M 小）。

第一個二分的實作跟一般的二分一樣，只是變成了看第二個二分的結果來決定調整上界還是下界。

而第二個二分，可以看到題目給定的公式如果固定 i 的值，該公式對於 j 是嚴格遞增。而反之並非如此。因此，可以窮舉每個 i 個值（也就是 0 ～ N － 1），並對每個 i 值二分出從哪個 j 值開始套入公式會大過 Q ，所以對於該 i 值會有 j － 1 個小過 Q 的值。然後將所有 i 值的加總，即可得知是否至少有 M － 1 個數字小過 Q 。

當外圈的二分結束以後，最終的 Q 值基本上為所求（如果條件稍微不一樣，就不保證 Q 在矩陣裡了）。

題外話：一開始這個題目漏洞百出，所以發生了一些好笑的事。有興趣可以到原題的討論區去看看。

本人的程式碼（於 CodePile 上）

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