自动搬运

查看原文

来自洛谷，原作者为

	Moya_Rao 麻烦各位给个关注嘛 qwq 蟹蟹啦 ^_^ || 加 QQ 粉丝群 1039915194 || 五升六女 OIer 一枚，称呼：lucky 猫 / lazy 猫 || 互关 /paste/vicj8uv2，粉福 /article/0hw27gsg

搬运于2025-08-24 22:54:34，当前版本为作者最后更新于2024-07-07 09:26:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

题目传送门 （翻译自 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，可放心看，但请不要直接提交我的代码。