1 条题解

  • 0
    @ 2024-2-28 20:16:00
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 5;
    int n, m, a[maxn], b[maxn];
    long long k;
    
    // 判断 <= x 的数是否 >= k 
    bool check(long long x) {
    	long long sum = 0;
    	for (int i = 1; i <= n; i++) {
    		if (a[i] >= 0) {
    			// a[i]*b[1], a[i]*b[2], ..., a[i]*b[m] 升序 
    			int l = 1, r = m, res = 0;
    			while (l <= r) {
    				int mid = (l + r) / 2;
    				if ((long long)a[i] * b[mid] <= x)
    					res = mid, l = mid + 1;
    				else 
    					r = mid - 1;
    			}
    			if (res) sum += res;
    		}
    		else {
    			// a[i]*b[1], a[i]*b[2], ..., a[i]*b[m] 降序
    			int l = 1, r = m, res = 0;
    			while (l <= r) {
    				int mid = (l + r) / 2;
    				if ((long long)a[i] * b[mid] <= x)
    					res = mid, r = mid - 1;
    				else 
    					l = mid + 1;
    			}
    			if (res) sum += m - res + 1;
    		}
    	}
    	return sum >= k;
    }
    
    int main() {
    	scanf("%d%d%lld", &n, &m, &k);
    	for (int i = 1; i <= n; i++)
    		scanf("%d", a+i);
    	for (int i = 1; i <= m; i++)
    		scanf("%d", b+i);
    	sort(a+1, a+n+1);
    	sort(b+1, b+m+1);
    	long long l = -1e18, r = 1e18, res;
    	while (l <= r) {
    		long long mid = (l + r) / 2;
    		if (check(mid)) 
    			res = mid, r = mid - 1;
    		else 
    			l = mid + 1;
    	}
    	printf("%lld\n", res);
    	return 0;
    }
    
    • 1

    信息

    ID
    77
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    2
    上传者