51Nod 1105 第K大的数

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\n",ans);
    return 0;
}