1084: 数学题

Time Limit:5000/3000 MS (Java/Others)   Memory Limit:163840/131072 KB (Java/Others) Total Submissions:803   Accepted:94 [ Submit][ Status][ Discuss]

Description

现在有两个数组 $A$和 $B$， 分别包含 $x$ 与 $y$个元素。定义一个新的数组 $C$， $C$ 中包含 $x\times y$ 个元素，为 $A$ 中所有元素除以 $B$中所有元素。即 新集合为 $｛c\mid c=\frac{a}{b}，a\in A，b\in B｝$。特殊地，$C$为多重集合。请求 $C$数组的第 $k$大数。

Input

第一行一个整数 $T$（$T\le 3$）表示方案数。对于每个方案：第一行三个整数 $n,m,k$（$0<n，m\le 100000，0<k\le n\times m$）第二行 $n$个正整数;第三行 $m$个正整数。数组中元素 $<{10}^8$。

Output

对于每个方案，输出一行：数组 $C$的第 $k$大数。结果四舍五入到两位小数。

Sample Input

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

Sample Output

1.67 2.00

分析：

              题意很明确，第一眼想到的肯定是暴力找，可惜复杂度达到O（mn）=10^10，显然是行不通的，所以需要算法优化。题目中要求的是一个数，或者我们可以理解为求的是一个解，那么想到什么？对，二分答案。多动动脑筋，不难想到将A，B数组分别排序后在O（m+n）复杂度下求出小于（大于）mid的C数组元素个数，题目要求答案精确到百分位，所以我是二分到10^-6，足够精确。整体复杂度约为O(nlogn + (m+n)log10^6)约为(m+n)logn的复杂度。

AC代码：

#include<iostream> #include<cstring> #include<math.h> #include<stdlib.h> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int Max = 1e5+5; const int mod = 1e9+7; double a[Max], b[Max]; bool cmp(double x, double y) {     return x>y; } int main( ) {     //freopen("input.txt","r",stdin);     int T;     cin>>T;     while(T--)     {         long long n, m, k;         cin>>n>>m>>k;         for(int i=0; i<n; i++)             scanf("%lf", a+i);         for(int i=0; i<m; i++)             scanf("%lf", b+i);         sort(a, a+n);//从小到大         sort(b, b+m, cmp);//从大到小         //二分初始化解的范围         double low = a[0]/b[0];         double high = a[n-1]/b[m-1];         while(high-low>1e-6)//二分的结果与解只差1e-6,可以AC了         {             int aa = 0, bb = 0;             double mid = (low+high)/2;             long long counter = 0;             //下面其实在O（2n+m）的复杂度下统计出比mid小的C数组元素个数             while(a[aa]/b[bb]<=mid && aa<n)                 aa++;             if(aa == n)                 aa--;             counter += aa+1;             bb++;             while(bb<m)             {                 while(a[aa]/b[bb]>mid)                     aa--;                 counter += aa+1;                 bb++;             }             counter = n*m-counter;             //这里可能比较难想清楚，假设第k-1大数为a，k大数为a，k+1大数为c，当此时mid已经非常接近解时：             if(counter >= k)//mid处于a，c之间，mid<=a,所以需要不断放大mid逼近a                 low = mid;             else//此时mid是处于a，b之间，mid>=a,所以需要不断缩小mid逼近a                 high = mid;         }         printf("%.2f\n", low);     }     return 0; }