北方高校联合训练第一周D-数学题-二分+尺取+单调性

奇奇怪怪的第一次北方高校联合训练，比赛时候只写出来一题……太惨了……这题看了题解后还想了半天……真的太菜了……
最近在写一个奇怪的py，本来这周不准备写题解想专心把奇怪的py写出来，不过这题很有意思，还是写个题解吧
题目链接

题意：有两个集合A，B（每个集合元素个数<=1e5）。集合C的定义是｛c∣c=a/b，a∈A，b∈B｝(其中/是小数除法)。现在给你集合A，B，问C中第k大的数是几，精确到两位小数。

思路：比赛的时候一神和高老师想到了二分，但是当时想万一这个二分到的数不存在怎么办，而且判断的时候继续对于一个集合中的元素枚举，另一个集合的元素二分，还有可能T掉，当时也就没写了……但是官方题解就是二分（个人猜测数据比较水，而且两位小数精度不够，卡卡就过去了），不过判断的时候并没有继续二分，而是利用了单调性。将A,B排序，pa指针指向A的最大元素，pb指针也指向B的最大元素，那么对于A中的每一元素，pb指针移动到最左边一个是(a[pa]/b[pb])<=x的位置之左（好吧，第一次没写等号也过了……数据真的太水了），这样pb之前的元素b[j]都能保证a[pa]/b[j]>x，pa指向的元素的大于x的贡献也就是pb。同时，这能够保证pb是单调向左移动的，因为当pa向左移动一位时，a[pa]/b[pb]的值是变小的，所以pb至少要向左移动才能使得a[pa]/b[pb]大于x。最后复杂度就是(m+n)10常数（常数取决于精度多少位，试了下，大于1e-3的精度是会wa的，所以二分的复杂度至少log（1e9））。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m,k;
long long total;
double eps=1e-4;
double a[100005],b[100005];
int check(double x)
{
	int pa=n,pb=m;
    long long cnt=0;
	while(pa>=1)
	{
		while((double)a[pa]/b[pb]<=x &&pb>=1)pb--;
		cnt+=pb;
		pa--;
	}
	//printf("%.2f:%d\n",x,cnt);
	if(cnt<k)return 1;
	 else return 0;
	
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&k);
		total=(long long)n*m;
		for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
		for(int i=1;i<=m;i++)scanf("%lf",&b[i]);
		sort(a+1,a+1+n);
		sort(b+1,b+1+n);
		double l=0,r=100000000;
		while(l<r-eps)
		{
			double mid=(l+r)/2.0;
			if(check(mid)==1)r=mid;  // ==1 大于k个 
			 else l=mid+eps;
		}
		//if(check(l)==1)r=l;
		printf("%.2f\n",r);
	}
	return 0;
}