P10091 [ROIR 2022 Day 2] 分数排序 题解

· · 题解

题目大意

题目传送门 （翻译自 ROIR 2022 D2T2）

给定 n 个分子和 n 个分母，将它们组合成 n^2 个分数，将第 c_i 小的分数约分后输出（参考代码里用 q 表示各个 c_i ，用 Q 表示 q 的个数）。

输出格式：若要输出 \dfrac{a}{b}，请输出 a b 。

思路

先将 a 数组和 b 数组都从小到大排个序。

排序后不难得出，\dfrac{a_j}{b_i}<\dfrac{a_j+1}{b_i}，\dfrac{a_j}{b_i}>\dfrac{a_j}{b_i+1}。可据此进行 check。当然精度得够高，在这里我们使用 long double 来操作。

那么二分出来的值如何匹配上正确的分母和分子呢？我们可以挨个儿去试，看看每个 b_i 可不可以对应上其中一个 a_j。我们可以使用 round 函数进行四舍五入（具体用法看这里，此题解默认你们会用）。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5 , AB = 1e6+5;
long long n,Q,a[N],b[N],q,p,g;
long double l,r;
bool v[AB];
bool check(long double k){
    long long j=0,sum=0;
    for(int i=1;i<=n;i++){
        while((long double)a[j+1]<(long double)k*b[i]&&j<n)j++;
        sum+=j;
    }
    return sum>=q;
}
long long gcd(long long x,long long y)
{
    if(x<y)swap(x,y);
    if(y==1)return y;
    if(x%y==0)return y;
    else return gcd(y,x%y);
}
int main(){
    scanf("%lld%lld",&n,&Q);
    for(int i=1;i<=n;i++){scanf("%lld",&a[i]);v[a[i]]=1;}
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    while(Q--){
        scanf("%lld",&q);
        l=(long double)a[1]/b[n];r=(long double)a[n]/b[1];
        while(r-l>=1e-13){
            long double mid=(l+r)/2;
            if(check(mid))r=mid;
            else l=mid;
        }
        for(int i=1;i<=n;i++){
            p=round(l*b[i]);
            if(p<=1e6&&v[p]&&abs(p-l*b[i])<1e-7){
                g=gcd(p,b[i]);
                printf("%lld %lld\n",p/g,b[i]/g);
                break;
            }
        }
    }
    return 0;
}

注：此代码已 AC，可放心看，但请不要直接提交我的代码。