https://ac.nowcoder.com/acm/contest/56825/E
题意
给你 \(10^{10}\) 个数(数组a n 个数,数组b m 个数,数是 a*b 的集合),有 \(Q\) (Q为常数)个询问,每次问你第 \(x\) 小的数是多少
思路
最暴力的思路肯定是把所有数放在一起,然后排序。易知时间复杂度为 \(nlogn(n = 1e10)\),会超时。
继续思考,如果给你一个数字,求它在 1e10 个数中的次序,可以在 On(双指针) / Onlogn(二分查找) 时间内解决。如果这个数字的次序大于x(第[>x]小),说明比答案偏大,让r=mid-1;反之让l=mid+1,然后就可以二分出答案啦。
时间复杂度 O(n * log2(n * m))
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
ll n, m, k, q, x;
ll a[N], b[N];
struct node{
int x, y;
}c[N * 10];
vector<ll> v;
ll Count(ll mid) {
ll res = 0; // mid是第几小 res个小于mid的
int ind = m;
for(int i = 1; i <= n; i++) {
while(a[i] * b[ind] >= mid) ind--;
res += ind;
}
for(auto i : v) {
if(i < mid) res--;
}
// cout << "mid: " << mid << " rank: " << res + 1 << endl; ////
return res + 1;
}
int main() {
cin >> n >> m >> k >> q;
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(int i = 1; i <= m; i++) scanf("%lld", &b[i]);
for(int i = 1; i <= k; i++) {
scanf("%d%d", &c[i].x, &c[i].y);
v.push_back(a[c[i].x] * b[c[i].y]);
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
while(q--) {
cin >> x;
ll l = 1, r = 1e18, mid, ans = -1;
while(l <= r) {
mid = (l + r) >> 1;
if(Count(mid) <= x) ans = mid, l = mid + 1;
else r = mid - 1;
}
printf("%lld\n", ans);
}
return 0;
}
标签:二分,10,int,res,ll,mid,牛客,72
From: https://www.cnblogs.com/re0acm/p/17397841.html