思路：

使用二分答案。

二分答案分为两部分：check 函数和二分。

二分楼上楼下都讲的很清楚了。

本题解只讲 check 函数。

首先：

  1. 先给 $a,b$ 数组排序。
  2. 总共有 $\Large \frac{a_i}{b_j}$ $>$ $\Large \frac{a_i}{b_{j+1}}$ 和 $\Large \frac{a_i}{b_j}$ $<$ $\Large \frac{a_i+1}{b_{j}}$。
  3. 最后双指针维护即可。

下放部分代码：

1
2
3
4
5
6
7
bool check(double k){
    int j=0,sum=0;
	for(int i=1;i<=n;i++){
		while(a[j+1]<k*b[i]&&j<n)j++;
		sum+=j;
	}return sum>=q;
}