10 第 K 个最小的素数分数----来源于陈C同学（CC）

来源于陈C同学（CC）

来源于陈C同学（CC）

来源于陈C同学（CC）

10 第 K 个最小的素数分数

作者: Turbo时间限制: 1S章节: 课程设计

问题描述 :

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数  组成，且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。

那么第 k 个最小的分数是多少呢?  

请输出相应的arr[i]和arr[j] 。

示例 1：

输入：

4

1 2 3 5

3

输出：

2 5

解释：已构造好的分数,排序后如下所示: 

1/5, 1/3, 2/5, 1/2, 3/5, 2/3

很明显第三个最小的分数是 2/5

示例 2：

输入：

2

1 7

1

输出：

1 7

输入说明 :

输入三行：

第一行输入一个整数n表示数组arr的长度。

第二行输入n个整数表示数组的元素。

第三行输入一个整数表示k.

提示：

    2 <= n <= 1000

    1 <= arr[i] <= 3 * 10^4

    arr[0] == 1

    arr[i] 是一个素数 ，i > 0

    arr 中的所有数字 互不相同 ，且按 严格递增 排序

    1 <= k <= n * (n - 1) / 2

输出说明 :

输出一行两个整数表示结果，整数间隔一个空格。

输入范例 :

#include
using namespace std;
 
typedef typename std::pair<int,int> MyPair;//first 分子，second 为分母
 
int arr[1005];
 
bool compare(MyPair a,MyPair b)
{
    return a.first*b.second
}
 
 
int main()
{
    int n,i,j,k;
    cin>>n;
    for(i=0;i
    {
        cin>>arr[i];
    }
    cin>>k;
    MyPair tmp;
    vector Fractions;
    for(i=0;i
    {
        for(j=i+1;j
        {
            tmp.first=arr[i];
            tmp.second=arr[j];
            Fractions.push_back(tmp);
        }
    }
 
    sort(Fractions.begin(),Fractions.end(),compare);
    cout<-1].first<<" "<-1].second;
    return 0;
}