# LeetCode 786. K-th Smallest Prime Fraction

https://leetcode.com/problems/k-th-smallest-prime-fraction/description/

## 題目大意

給定已排序的整數陣列 `arr`，裡面包含了 `1` 和質數，而且 `arr` 中所有整數全相異
題目還給了一個整數 `k`

對於 `arr` 中的每一對 `i` 和 `j`，考慮分數 `arr[i] / arr[j]` (`i` $\lt$ `j`)

回傳第 `k` 小的分數
其中 `answer[0] == arr[i]` 、 `answer[1] == arr[j]`

## 思考

因為題目排序過，所以如果問最小的，那肯定是頭除以尾
不過這題問的是第 `k` 個……

等等，想到了嗎？問第 `k` 個，不過題目有幫我們**排序**過了……

是的，這題我們可以用 binary search ，排序過算是一個提示

class Solution
{
public:
    vector<int> kthSmallestPrimeFraction(vector<int> &arr, int k)
    {
        double l = 0, r = 1;
        const int n = arr.size();

        while (l < r)
        {
            const double mid = (l + r) / 2.0;
            int p = 0, q = 1, cnt = 0;

            for (int i = 0, j = 1; i < n; ++i)
            {
                while (j < n && arr[i] > mid * arr[j])
                    ++j;

                if (j == n)
                    break;

                cnt += n - j;
                if (p * arr[j] < q * arr[i])
                {
                    p = arr[i];
                    q = arr[j];
                }
            }

            if (cnt == k)
                return {p, q};

            if (cnt < k)
                l = mid;
            else
                r = mid;
        }

        throw;
    }
};

對於每個 `i` ，我們先找到第一個 `j` 滿足 $\frac{\mathrm{arr}[i]}{\mathrm{arr}[j]} \le mid$

那麼我們就知道不大於 `mid` 的分數總共有 `n - j` 個
這是本題的一大關鍵想法

然後我們每次都要更新 $\frac{p}{q}$ 成最大

最後，如果 `cnt == k` 即為題意