两个数组各个数相加或相乘变成一个矩阵求第K大

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

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 int a[MAXN], b[MAXN];

 int T, n;

 LL k;

 bool check(int val)//统计比val小的数的个数cnt，看cnt比k大还是比k小

 {

     LL cnt = ;

     for(int i = , j = n - ; i < n; ++i)

     {

         while(j >=  && a[i] * b[j] > val) --j;

         cnt += j + ;//j+1指每一列数中比val大的数

     }

     return cnt >= k;

 }

 int solve()//二分查找第k大的数

 {

     int l = a[] * b[], r = a[n - ] * b[n - ];

     while(l < r)

     {

         int mid = (l + r) >> ;

         if(!check(mid)) l = mid + ;

         else r = mid;

     }

     return l;

 }

 int main()

 {

     scanf("%d", &T);

     while (T--)

     {

         scanf("%d%I64d", &n, &k);

         for(int i = ; i < n; ++i) scanf("%d", &a[i]);

         for(int i = ; i < n; ++i) scanf("%d", &b[i]);

         sort(a, a + n);

         sort(b, b + n);

         k = (LL)n * n - k + ;

         printf("%d\n", solve());

     }

     return ;

 }

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]

两个数组各个数相加或相乘变成一个矩阵求第K大的相关教程结束。