input
1<=T<=20
1<=n<=100000,1<=k<=n*n
a1 a2 ... an 0<ai<=10000
b1 b2 ... bn 0<bi<=10000
output
第k大的数（包含重复）
做法：类似字符串的编码解码，这里是解码过程，将k解码为对应的01串，把第K大的数看成一个01串，统计出比1000000000000000000000000000000000大的数有多少个，从而确定第一个数是0还是1，然后第二位也是这样，不断的重复直到找到第K大的数，复杂度为O(2nlog(maxa*maxb))
a[0]*b[0]<=a[0]*b[1]<=...<=a[0]*b[n-1]
a[1]*b[0]<=a[1]*b[1]<=..<=a[1]*b[n-1]
...
a[n-1]*b[0]<=a[n-1]*b[1]<=...<=a[n-1]*b[n-1]
同时从上到下也有这样的性质，所以当a[i]*b[j]>val时，a[i+1]*b[j]>val
1 #include2 #include 3 #include 4 using namespace std; 5 typedef long long LL; 6 7 const int MAXN = 100010; 8 9 int a[MAXN], b[MAXN];10 int T, n;11 LL k;12 13 bool check(int val)//统计比val小的数的个数cnt，看cnt比k大还是比k小14 {15 LL cnt = 0;16 for(int i = 0, j = n - 1; i < n; ++i)17 {18 while(j >= 0 && a[i] * b[j] > val) --j;19 cnt += j + 1;//j+1指每一列数中比val大的数20 }21 return cnt >= k;22 }23 24 int solve()//二分查找第k大的数25 {26 int l = a[0] * b[0], r = a[n - 1] * b[n - 1];27 while(l < r)28 {29 int mid = (l + r) >> 1;30 if(!check(mid)) l = mid + 1;31 else r = mid;32 }33 return l;34 }35 36 int main()37 {38 scanf("%d", &T);39 while (T--)40 {41 scanf("%d%I64d", &n, &k);42 for(int i = 0; i < n; ++i) scanf("%d", &a[i]);43 for(int i = 0; i < n; ++i) scanf("%d", &b[i]);44 sort(a, a + n);45 sort(b, b + n);46 k = (LL)n * n - k + 1;47 printf("%d\n", solve());48 }49 return 0;50 }
input
1<=T<=10
1<=n,k<=100000
a1 a2 ... an an<=10^9
b1 b2 ... bn bn<=10^9
output
第k小的数（不包含重复）
做法：用大白上的有限队列做法，先将第一列的数放进从小到大的优先队列，每出队一个数就将同一行的下一个数放入队列
a[0]+b[0]<=a[0]+b[1]<=...<=a[0]+b[n-1]
a[1]+b[0]<=a[1]+b[1]<=..<=a[1]+b[n-1]
...
a[n-1]+b[0]<=a[n-1]+b[1]<=...<=a[n-1]+b[n-1]