zcmu 1540: 第k大数

86 阅读 0 评论 57 点赞

我是靠谱客的博主迷路发带，最近开发中收集的这篇文章主要介绍zcmu 1540: 第k大数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

有两个序列a，b，它们的长度分别为n和m，那么将两个序列中的元素对应相乘后得到的n*m个元素从大到小排列后的第k个元素是什么？

Input

输入的第一行为一个正整数T (T<=10)，代表一共有T组测试数据。

每组测试数据的第一行有三个正整数n，m和k(1<=n, m<=100000,1<=k<=n*m)，分别代表a序列的长度，b序列的长度，以及所求元素的下标。第二行为n个正整数代表序列a。第三行为m个正整数代表序列b。序列中所有元素的大小满足[1,100000]。

Output

对于每组测试数据，输出一行包含一个整数代表第k大的元素是多少。

Sample Input

33 2 31 2 31 22 2 11 11 12 2 41 11 1

Sample Output

311

HINT

code：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<math.h>
#include<string.h>
#include<stdlib.h>

using namespace std;
typedef long long ll;

ll n,m,k;
ll a[100005],b[100005];

bool cmp(ll a,ll b){
    return a>b;
}

ll f(ll x){
    ll num=0;  //大于等于x的个数；
    ll i=0,j=n-1;
    for(;i<n&&j>=0;i++){ //随着i增加，a[i]*b[j]在变小；
        if(a[i]*b[j]>=x)   //a[0]最大b[m-1]最小，当a[0]*b[m-1]>=x时，那>=x的还有m-1种；
            num=num+j+1;
        else{
            while(j>=0&&a[i]*b[j]<x)
                j--;
            if(j>=0)
                num=num+j+1;
        }
    }
    return num;
}

void bs(){
    ll left=a[n-1]*b[n-1];  //最小值
    ll right=a[0]*b[0];   //最大值
    ll r=0;
    while(left<=right){
        ll mid=(left+right)>>1;//相当于除2，但这个速度更快；
        if(f(mid)>=k){ //不能用if（f(mid)==k）这个方法。
            left=mid+1;
            r=mid;
        }
        else
            right=mid-1;
    }
    printf("%lldn",r);
}


int main(){
  //  freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lld %lld %lld",&n,&m,&k);
        for(ll i=0;i<n;i++)
            scanf("%lld",&a[i]);
        for(ll i=0;i<m;i++)
            scanf("%lld",&b[i]);
        sort(a,a+n,cmp);
        sort(b,b+m,cmp);
        bs();
    }
    return 0;
}