太仓网站开发,wordpress留言板,长沙装修公司前十强,002822中装建设股吧Description 现在有两个数组 AA 和 BB#xff0c; 分别包含 xx 与 yy 个元素。 定义一个新的数组 CC#xff0c; CC 中包含 xyxy 个元素#xff0c;为 AA 中所有元素除以 BB 中所有元素。 即 新集合为 #xff5b;c∣cab#xff0c;a∈A#xff0c;b∈B#xff5d;… Description 现在有两个数组 AA 和 BB 分别包含 xx 与 yy 个元素。 定义一个新的数组 CC CC 中包含 x×yx×y 个元素为 AA 中所有元素除以 BB 中所有元素。 即 新集合为 c∣caba∈Ab∈Bc∣caba∈Ab∈B 。特殊地CC 为多重集合。 请求 CC 数组的第 kk 大数。 Input 第一行一个整数 TTT≤3T≤3表示方案数。 对于每个方案 第一行三个整数 n,m,kn,m,k0nm≤1000000k≤n×m0nm≤1000000k≤n×m 第二行 nn 个正整数; 第三行 mm 个正整数。 数组中元素 108108。 Output 对于每个方案输出一行 数组 CC 的第 kk 大数。结果四舍五入到两位小数。 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 题解这个题乍一看想FFT其实没有那么麻烦只是个简单的二分答案。 如果一个数是第K大的数那么一定存在至少K个数小于等于它把这个作为二分的条件。
如何判断有K个数小于等于它呢好像不是很好判断我们转换为计算大于x的数的个数。
我们可以把A数组和B数组排序然后用双指针指针Pa指向数组A的左端指针Pb指向数组B的左端这样固定Pa把Pb像右移动直到(*Pa)/(*Pb) x为止然后Pa向右移动一个再循环这个操作直到Pa到头或者Pb到头可以证明Pb始终不需要掉头
check函数的代码 int check(double x)
{int tot 0;int pos 0; for(int i 0;i N;i){while(pos M (double)A[i]/(double)B[pos] x) pos;tot pos;}return tot;
}代码#include cstdio
#include iostream
#include algorithm
using namespace std;
const int MAX 100005;
const double EPS 0.001;
int A[MAX],B[MAX];
int N,M,K;
int check(double x)
{int tot 0;int pos 0; for(int i 0;i N;i){while(pos M (double)A[i]/(double)B[pos] x) pos;tot pos;}return tot;
}
int main()
{int T;scanf(%d,T);while(T--){scanf(%d%d%d,N,M,K) ;for(int i 0;i N;i) scanf(%d,A[i]);for(int i 0;i M;i) scanf(%d,B[i]);sort(A,A N);sort(B,B M);double l 0,r A[N-1];while(r - l EPS){double mid (r l) /2;if(check(mid) K) r mid;//检查大于mid的数有多少个 else l mid; }printf(%.2f\n,l);}return 0;} /*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*/
