题面

7-6 1F. 乘法  

给出一个长度为 n 的数列 和一个长度为 m 的数列 ，可以构造得到一个 n×m 的矩阵 C，其中 C​i,j​​=A​i​​×B​j​​。

给出整数 K，你需要求出 C 中第 K 大的数的值。

输入格式：

第一行输入三个整数 ,。

第二行输入 n 个空格隔开的整数 ,

第三行输入 m 个空格隔开的整数 ,

输出格式

输出一行一个整数，表示矩阵中的第 K 大的数的值。

输入样例：

3 3 3
2 3 4
4 5 6

 

输出样例：

18

作者: 2020,Winter,Day1 单位: 东北大学秦皇岛分校 时间限制: 1000 ms 内存限制: 256 MB 代码长度限制: 16 KB  

题解

对于答案 二分即可，差找比这个值大的输有几个，相等的有几个，然后就可以check这个值是否则正确。

关键在于怎么区遍历整个矩阵查找。

要是只有正数要好做许多。

对于全是正数而言：

直接 A * B复杂度直接boom，可以先排序，外循环从小到大，内循环从大到小，保证内循环使得乘积不断变小，记下满足条件的内循环时 j 的值，然后++i，乘积变大，但保证与对于之前循环过的 j 位置的数相乘乘积大于阈值，

这样就减少了内层循环，使得 i， j实际一个变大，一个表变小，实现 复杂度 A + B 而不是 A * B。

现在再考虑正负，分情况讨论即可，只要保证两个循环不会回退，实现 复杂度相加即可，分成两种就行，我弄麻烦了，分成了 A非负、A负、B非负、B负四部分，相对麻烦一这些。

 

代码如下

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <queue>
  4 #include <cmath>
  5 
  6 #define RE register
  7 #define FOR(i,a,b) for(RE int i=a;i<=b;++i)
  8 #define ROF(i,a,b) for(RE int i=a;i>=b;--i)
  9 #define sc(n) scanf("%d",&n)
 10 #define ll long long
 11 
 12 using namespace std;
 13 
 14 const int MAXN = 100010;
 15 
 16 int a[MAXN], b[MAXN], tota, totb;
 17 int x[MAXN], y[MAXN], totx, toty;
 18 int T, n, m;
 19 ll k;
 20 
 21 int check(long long val)
 22 {
 23     ll cnt = 0, tot = 0;
 24     for (int i = 0, j = totb - 1; i < tota && cnt < k; ++i)
 25     {
 26         while (j >= 0 && 1ll * a[i] * b[j] > val) --j;
 27         cnt += (1ll * totb - j - 1);
 28         int jj = j;
 29         while (jj >= 0 && 1ll * a[i] * b[jj] == val) --jj, ++tot;
 30     }
 31     for (int i = tota - 1, j = toty - 1; i >= 0 && cnt < k; --i)
 32     {
 33         while (j >= 0 && 1ll * a[i] * y[j] > val) --j;
 34         cnt += (1ll * toty - j - 1);
 35         int jj = j;
 36         while (jj >= 0 && 1ll * a[i] * y[jj] == val) --jj, ++tot;
 37     }
 38     for (int i = totb - 1, j = totx - 1; i >= 0 && cnt < k; --i)
 39     {
 40         while (j >= 0 && 1ll * b[i] * x[j] > val) --j;
 41         cnt += (1ll * totx - j - 1);
 42         int jj = j;
 43         while (jj >= 0 && 1ll * b[i] * x[jj] == val) --jj, ++tot;
 44     }
 45     for (int i = totx - 1, j = 0; i >= 0 && cnt < k; --i)
 46     {
 47         while (j < toty && 1ll * x[i] * y[j] > val) ++j;
 48         cnt += j;
 49         int jj = j;
 50         while (jj < toty && 1ll * x[i] * y[jj] == val) ++jj, ++tot;
 51     }
 52     if (cnt < k && cnt + tot >= k)return -1;
 53     if (cnt < k) return 1;
 54     return 0;
 55 }
 56 
 57 ll solve()//二分查找第k大的数
 58 {
 59     ll l = 1e13, r = -1e13;
 60     if (totx && totb) l = min(l, 1ll * x[0] * b[totb - 1]);
 61     if (toty && tota) l = min(l, 1ll * y[0] * a[tota - 1]);
 62     if (totx && toty) l = min(l, 1ll * y[toty - 1] * x[totx - 1]);
 63     if (tota && totb) l = min(l, 1ll * a[0] * b[0]);
 64 
 65     if (totx && totb) r = max(r, 1ll * x[totx - 1] * b[0]);
 66     if (toty && tota) r = max(r, 1ll * y[toty - 1] * a[0]);
 67     if (totx && toty) r = max(r, 1ll * y[0] * x[0]);
 68     if (tota && totb) r = max(r, 1ll * a[tota - 1] * b[totb - 1]);
 69     while (l < r)
 70     {
 71         ll mid = (l + r) >> 1;
 72         int ans = check(mid);
 73         if (ans == -1)return mid;
 74         if (ans) r = mid;
 75         else l = mid + 1;
 76     }
 77     return l;
 78 }
 79 
 80 int main()
 81 {
 82     scanf("%d%d%lld", &n, &m, &k);
 83     for (int i = 0; i < n; ++i)
 84     {
 85         sc(T);
 86         if (T >= 0)a[tota++] = T;
 87         else x[totx++] = T;
 88     }
 89     for (int i = 0; i < m; ++i)
 90     {
 91         sc(T);
 92         if (T >= 0)b[totb++] = T;
 93         else y[toty++] = T;
 94     }
 95     sort(a, a + tota);
 96     sort(x, x + totx);
 97     sort(b, b + totb);
 98     sort(y, y + toty);
 99     printf("%lld\n", solve());
100     return 0;
101 }