P10091 [ROIR 2022] 分数排序 (Day 2)

题目背景

翻译自 ROIR 2022 D2T2。

题目描述

有两个由 $n$ 个不同整数组成的序列 $A=[a_1,a_2,\dots ,a_n]$ 和 $B=[b_1,b_2,\dots ,b_n]$。将它们组合成 $n^2$ 个分数，形式为 $\frac{a_i}{b_j}$，并将每个分数约分后按递增顺序排序。

给定一个数字 $q$ 和 $q$ 个整数 $c_1,c_2,\dots ,c_q$。对于每个 $c_i$，请输出上面所说的 $n^2$ 个分数中第 $c_i$ 小的分数。

输入格式

第一行包含两个整数 $n$ 和 $q$。

第二行包含 $n$ 个不同的整数 $a_1,a_2,\dots ,a_n$。

第三行包含 $n$ 个不同的整数 $b_1,b_2,\dots ,b_n$。

第四行包含 $q$ 个不同的整数 $c_1,c_2,\dots ,c_q$。

输出格式

输出 $q$ 行。第 $i$ 行输出按递增顺序得到的第 $c_i$ 个分数。分数 $\frac{p}{q}$ 应以 p q 的格式输出，并且应为最简分数。

输入输出样例 #1

输入 #1

4 8
3 4 1 2
2 3 4 5
1 16 2 4 5 6 10 15

输出 #1

1 5
2 1
1 4
2 5
1 2
1 2
4 5
3 2

说明/提示

在样例中，初始的分数列表如下：

$$\left[\frac{3}{2},\frac{3}{3},\frac{3}{4},\frac{3}{5},\frac{4}{2},\frac{4}{3},\frac{4}{4},\frac{4}{5},\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\frac{2}{2},\frac{2}{3},\frac{2}{4},\frac{2}{5}\right],$$

经过约分后，得到：

$$\left[\frac{3}{2},\frac{1}{1},\frac{3}{4},\frac{3}{5},\frac{2}{1},\frac{4}{3},\frac{1}{1},\frac{4}{5},\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\frac{1}{1},\frac{2}{3},\frac{1}{2},\frac{2}{5}\right],$$

最后按递增顺序排序，得到：

$$\left[\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1},\frac{1}{1},\frac{1}{1},\frac{4}{3},\frac{3}{2},\frac{2}{1}\right].$$

本题使用捆绑测试。

子任务	分值	特殊性质
$1$	$14$	$n\le 50$
$2$	$13$	$n\le 500$
$3$	$15$	$q,c_i\le 100$
$4$	$21$	$c_i\le 10^5$
$5$	$37$

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le q\le 10^5$ 且 $q\le n^2,n\times q\le 10^5$（所以实际上 $q\le 1000\sqrt[3]{10}\approx 2154$），$1\le a_i,b_i\le 10^6$，$1\le c_i\le n^2$。

C++实现

#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[100010],b[100010];
long long check(long double x){
	int j=0;
	long long sum=0;
	for(int i=1;i<=n;i++){
		while((long double)a[j+1]<(long double)x*b[i]&&j<n) j++;
		sum+=j;
	}
	return sum;
}
bool p[1000010];
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),p[a[i]]=1;
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	while(q--){
		long long c;
		scanf("%lld",&c);
		long double 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)>=c) r=mid;
			else l=mid;
		}
		for(int i=1;i<=n;i++){
			int fz=round(l*b[i]);//尝试l*b[i]做分子
			if(fz<=1e6&&p[fz]&&abs(fz-l*b[i])<1e-7){
				int g=__gcd(fz,b[i]);
				printf("%d %d\n",fz/g,b[i]/g);
				break;
			}
		}
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容