ZOJ-3278 8G Island---二分第k大

题目链接：

https://cn.vjudge.net/problem/ZOJ-3278

题目大意：

给出两个数列A和B，长度分别为N，M (1<=N, M<=10^5, 1<=Ai, Bi<=10^5)，求Cij = Ai * Bj中第K大的数

解题思路：

二分第k大，然后枚举a[i]，二分b[i]来判断是不是第k大

注意long long

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5 + 10;
 4 typedef long long ll;
 5 ll a[maxn], b[maxn];
 6 ll n, m, k;
 7 ll judge(ll x)
 8 {
 9     ll tot = 0;
10     for(int i = 1; i <= n; i++)
11     {
12         ll tmp = x / a[i];
13         int t = upper_bound(b + 1, b + 1 + m, tmp) - b;
14         if(t > m || b[t] > tmp)t--;
15         //t > m 说明tmp大于b的最大值，此时t为m+1,需要减一表示小于等于tmp的数目
16         tot += t;//此时的t表示小于等于tmp的数目
17     }
18     return tot;
19 }
20 int main()
21 {
22     while(scanf("%lld%lld%lld", &n, &m, &k) != EOF)
23     {
24         k = n * m + 1 - k;
25         for(int i = 1; i <= n; i++)
26             scanf("%lld", &a[i]);
27         for(int i = 1; i <= m; i++)
28             scanf("%lld", &b[i]);
29         sort(b + 1, b + 1 + m);
30         ll l = 1, r = 1e10, ans;
31         while(l <= r)
32         {
33             ll m = (l + r) / 2;
34             if(judge(m) >= k)ans = m, r = m - 1;
35             else l = m + 1;
36         }
37         cout<<ans<<endl;
38     }
39     return 0;
40 }