leetcode786 第 K 个最小的素数分数

思路：
二分。
实现：
 1 class Solution
 2 {
 3 public:
 4     bool check(double x, vector<int>& arr, int k)
 5     {
 6         int slow = 0, n = arr.size(), ans = 0;
 7         for (int i = 1; i < n; i++)
 8         {
 9             if (arr[slow] > x * arr[i]) continue;
10             int tmp = slow;
11             while (slow < i and arr[slow] <= x * arr[i]) slow++;
12             ans += (slow - tmp) * (n - i);
13         }
14         return ans >= k;
15     }
16     vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k)
17     {
18         int n = arr.size();
19         double l = 0, r = 1, res = -1;
20         for (int i = 0; i < 30; i++)
21         {
22             double m = (l + r) / 2;
23             if (check(m, arr, k))
24             {
25                 res = m; r = m;
26             }
27             else l = m;
28         }
29         double minn = 0x3f3f3f3f;
30         int a = -1, b = -1;
31         for (int i = 0; i < n; i++)
32         {
33             double x = res * arr[i];
34             int p = upper_bound(arr.begin(), arr.begin() + i, x) - arr.begin();
35             if (p)
36             {
37                 p--;
38                 double tmp = (double)arr[p] / arr[i];
39                 if (abs(res - tmp) < minn)
40                 {
41                     minn = abs(res - tmp);
42                     a = p; b = i;
43                 }
44             }
45         }
46         return vector<int>{arr[a], arr[b]};
47     }
48 };