首页 > 代码库 > Dwarf Tower
Dwarf Tower
第K小数
( number .cpp/c/pas)
【问题描述】
有两个正整数数列，元素个数分别为N和M。从两个数列中分别任取一个数相乘，这样一共可以得到N*M个数，询问这N*M个数中第K小数是多少。
【输入格式】
输入文件名为number.in。
输入文件包含三行。
第一行为三个正整数N,M和K。
第二行为N个正整数，表示第一个数列。
第三行为M个正整数，表述第二个数列。
【输出格式】
输出文件名为number.out。
输出文件包含一行，一个正整数表示第K小数。
【输入输出样例1】
number.in number.out
2 3 4
1 2
2 1 3
3
【输入输出样例2】
number.in number.out
5 5 18
7 2 3 5 8
3 1 3 2 5
16
【数据规模与约定】
//二分+数学思想 #include<cstdio>#include<algorithm>using namespace std;long long n,m,k;long long a[200001],b[200001],mid;int main(){ scanf("%lld%lld%lld",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%lld",a+i); for(int i=1;i<=m;i++) scanf("%lld",b+i); sort(a+1,a+n+1); sort(b+1,b+m+1); long long l=0,r=a[n]*b[m]+1; while(l+1<r){ mid=(l+r)/2; long long sum=0,p=m; for(int i=1;i<=n;i++){ while(p>=0&&a[i]*b[p]>=mid) p--;//sum记录比mid小的个数； sum+=(p); } if(sum>=k) r=mid; else l=mid; } printf("%lld\n",l); return 0;}
Dwarf Tower
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。