STL求第k大的元素-白红宇

STL求第k大的元素

阅读量：4205 次

发布时间：2019-05-26

本文共 898 字，大约阅读时间需要 2 分钟。

Description

现在有两个数组 $A$ 和 $B$ ，分别包含 $x$ 与 $y$ 个元素。

定义一个新的数组 $C$ ， $C$ 中包含 $x \times y$ 个元素，为 $A$ 中所有元素除以 $B$ 中所有元素。

即新集合为 $｛ c ∣ c = \frac{a}{b} ， a \in A ， b \in B ｝$ 。特殊地， $C$ 为多重集合。

请求 $C$ 数组的第 $k$ 大数。

Input

第一行一个整数 $T$ （ $T \leq 3$ ）表示方案数。

对于每个方案：

第一行三个整数 $n, m, k$ （ $0 < n ， m \leq 100000 ， 0 < k \leq n \times m$ ）

第二行 $n$ 个正整数;

第三行 $m$ 个正整数。

数组中元素 $< 10^{8}$ 。

Output

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

数组 $C$ 的第 $k$ 大数。结果四舍五入到两位小数。

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 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            using namespace std;double a[100010],b[100010];multiset
            
             mset;multiset
             
              ::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