Problem
数组A和数组B，里面都有n个整数。
数组C共有n^2个整数，分别是：
A[0] * B[0],A[0] * B[1] ...... A[0] * B[n-1]
A[1] * B[0],A[1] * B[1] ...... A[1] * B[n-1]
......
A[n - 1] * B[0],A[n - 1] * B[1] ...... A[n - 1] * B[n - 1]
是数组A同数组B的组合,求数组C中第K大的数。
例如：
A：1 2 3，B：2 3 4。
A与B组合成的C为
A[0] A[1] A[2]
B[0] 2 3 4
B[1] 4 6 8
B[2] 6 9 12
共9个数。
Solution
一种二分套二分，二分答案，check的时候对每个数二分找更小的，有一些细节需要处理。
仔细考虑发现，找比二分的数小的数，只要扫一遍，另一个指针随时减。省掉一个log
Code1
#include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<string.h>
#include<queue>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAXN=50020;
ll n,k,a[MAXN],b[MAXN];
ll cont(int cur,ll num){
ll t=a[cur],ans=0;
int l=1,r=n,mid;
while(l<=r){
mid=(l+r)/2;
if(t*b[mid]<=num){
l=mid+1;
ans=mid;
}
else{
r=mid-1;
}
}
return ans;
}
bool check(ll x){
ll ans=0;
for(int i=1;i<=n;i++){
ans+=cont(i,x);
}
return ans>=k;
}
int main() {
io_opt;
cin>>n>>k;
k=n*n-k+1;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
ll l=a[1]*b[1],r=a[n]*b[n],mid,ans;
while(l<=r){
mid=(l+r)/2;
if(check(mid)){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
cout<<ans<<endl;
return 0;
}
Code2
#include<stdio.h>
#include<set>
//#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<string.h>
#include<queue>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
//using namespace std;
const int MAXN=50020;
ll n,k,a[MAXN],b[MAXN];
inline ll cont(int cur,ll num){
ll t=a[cur],ans=0;
int l=1,r=n,mid;
while(l<=r){
mid=(l+r)/2;
if(t*b[mid]<=num){
l=mid+1;
ans=mid;
}
else{
r=mid-1;
}
}
return ans;
}
inline bool check(ll x){
ll ans=0;
int j=n;
for(int i=1;i<=n;i++){
while(a[i]*b[j]>x) j--;
ans+=j;
}
return ans>=k;
}
int main() {
//io_opt;
scanf("%lld%lld",&n,&k);
k=n*n-k+1;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&a[i],&b[i]);
}
std::sort(a+1,a+1+n);
std::sort(b+1,b+1+n);
ll l=a[1]*b[1],r=a[n]*b[n],mid,ans=r;
while(l<=r){
mid=(l+r)/2;
if(check(mid)){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
printf("%lld
",ans);
return 0;
}