1540: 第k大数 两个数组元素相乘后的第k大( 二分答案 + 输入输
发布时间:2020-12-14 02:38:15 所属栏目:大数据 来源:网络整理
导读:1540: 第k大数 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 104 Solved: 6 [Submit][Status][Web Board] Description 有两个序列a,b,它们的长度分别为n和m,那么将两个序列中的元素对应相乘后得到的n*m个元素从大到小排列后的第k个元素是什么? Inpu
1540: 第k大数
Time Limit: 10 Sec Memory Limit: 128 MB Submit: 104 Solved: 6 [Submit][Status][Web Board] Description 有两个序列a,b,它们的长度分别为n和m,那么将两个序列中的元素对应相乘后得到的n*m个元素从大到小排列后的第k个元素是什么? Input 输入的第一行为一个正整数T (T<=10),代表一共有T组测试数据。 每组测试数据的第一行有三个正整数n,m和k(1<=n,m<=100000,1<=k<=n*m),分别代表a序列的长度,b序列的长度,以及所求元素的下标。第二行为n个正整数代表序列a。第三行为m个正整数代表序列b。序列中所有元素的大小满足[1,100000]。 Output 对于每组测试数据,输出一行包含一个整数代表第k大的元素是多少。 Sample Input 3 3 2 3 1 2 3 1 2 2 2 1 1 1 1 1 2 2 4 1 1 1 1 Sample Output 3 1 1 #include<bits/stdc++.h> using namespace std; template<class T>inline T read(T&x) { char c; while((c=getchar())<=32)if(c==EOF)return 0; bool ok=false; if(c=='-')ok=true,c=getchar(); for(x=0; c>32; c=getchar()) x=x*10+c-'0'; if(ok)x=-x; return 1; } template<class T> inline T read_(T&x,T&y) { return read(x)&&read(y); } template<class T> inline T read__(T&x,T&y,T&z) { return read(x)&&read(y)&&read(z); } template<class T> inline void write(T x) { if(x<0)putchar('-'),x=-x; if(x<10)putchar(x+'0'); else write(x/10),putchar(x%10+'0'); } template<class T>inline void writeln(T x) { write(x); putchar('n'); } //-------ZCC IO template------ const int maxn=1e5+1; const double inf=999999999; #define lson (rt<<1),L,M #define rson (rt<<1|1),M+1,R #define M ((L+R)>>1) #define For(i,t,n) for(int i=(t);i<(n);i++) typedef long long LL; typedef double DB; typedef pair<int,int> P; #define bug printf("---n"); #define mod 1000000007 int a[maxn],b[maxn]; int n,m,k; bool pan(LL num) { int cnt=0; for(int i=0;i<n;i++) cnt+=m-(upper_bound(b,b+m,num/a[i])-b);//查找是否比num大的元素的个数 // printf("num=%lld cnt=%dn",num,cnt); return cnt>k-1; } void slove() { LL l=(LL)a[0]*b[0]; LL h=(LL)a[n-1]*b[m-1];//在最大最小值之间二分答案 while(l<=h) { LL mid=(LL)(l+h)/2; if(pan(mid)) l=mid+1; else h=mid-1; } writeln(l); } int main() { int T; //freopen("in.txt","r",stdin); read(T); while(T--) { read__(n,k); For(i,n)read(a[i]); For(i,m)read(b[i]); sort(a,a+n); sort(b,b+m); slove(); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |