1 条题解
-
0
#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
- 上传者