STL求第k大的元素

Description

现在有两个数组 AA 和 BB， 分别包含 xx 与 yy 个元素。

定义一个新的数组 CC， CC 中包含 x×yx×y 个元素，为 AA 中所有元素除以 BB 中所有元素。

即 新集合为 ｛c∣c=ab，a∈A，b∈B｝｛c∣c=ab，a∈A，b∈B｝ 。特殊地，CC 为多重集合。

请求 CC 数组的第 kk 大数。

Input

第一行一个整数 TT（T≤3T≤3）表示方案数。

对于每个方案：

第一行三个整数 n,m,kn,m,k（0<n，m≤100000，0<k≤n×m0<n，m≤100000，0<k≤n×m ）

第二行 nn 个正整数;

第三行 mm 个正整数。

数组中元素 <108<108。

Output

对于每个方案，输出一行：

数组 CC 的第 kk 大数。结果四舍五入到两位小数。

Sample Input

25 5 31 2 3 4 52 3 4 5 65 5 21 2 3 4 52 3 4 5 6
Sample Output
1.67
2.00
////  main.cpp//  周赛一////  Created by liuzhe on 16/6/1.//  Copyright © 2016年 my_code. All rights reserved.//#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <cstring>#include <cmath>#include <set>#include <map>#include <iostream>using namespace std;double a[100010],b[100010];multiset<double>mset;multiset<double>::iterator it;int main(){    int t;    scanf("%d",&t);    while(t--)    {        mset.clear();        int n,m,k;        scanf("%d%d%d",&n,&m,&k);        for(int i=0;i<n;i++)            scanf("%lf",&a[i]);        for(int i=0;i<m;i++)            scanf("%lf",&b[i]);        double x;        for(int i=0;i<n;i++)            for(int j=0;j<m;j++)            {                x=a[i]/b[j];                mset.insert(x);            }        int w=n*m-k;        for(it=mset.begin();it!=mset.end();it++)        {            if(!w)                break;            w--;        }        PRintf("%.2lf/n",*it);    }    return 0;}