首页 > 代码库 > 51nod 1105 第K大的数
51nod 1105 第K大的数
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
数组A和数组B，里面都有n个整数。数组C共有n^2个整数，分别是A[0] * B[0],A[0] * B[1] ......A[1] * B[0],A[1] * B[1]......A[n - 1] * B[n - 1]（数组A同数组B的组合）。求数组C中第K大的数。
例如：A：1 2 3，B：2 3 4。A与B组合成的C包括2 3 4 4 6 8 6 9 12共9个数。
Input
第1行：2个数N和K，中间用空格分隔。N为数组的长度，K对应第K大的数。(2 <= N <= 50000，1 <= K <= 10^9)第2 - N + 1行：每行2个数，分别是A[i]和B[i]。(1 <= A[i],B[i] <= 10^9)
Output
输出第K大的数。
Input示例
3 21 22 33 4
Output示例
9
二分
A,B数组分别排序
左端点为A[1]*B[1] 右端点A[n]*B[n]
找比mid小的数有多少个
若满足条件 更新答案
屠龙宝刀点击就送
#include <algorithm>#include <cstdio>typedef long long LL;using namespace std;LL cnt=0,n,k,A[50050],B[50050];LL check(LL now){ LL ans=0; for(LL i=1;i<=n;i++) { LL l=1,r=n,num=0; while(l<=r) { LL mid=(l+r)>>1; if(A[i]*B[mid]<now) num=mid,l=mid+1; else r=mid-1; } ans+=num; } return ans<k?1:0;}int main(){ scanf("%lld%lld",&n,&k);k=(n*n)-k+1; for(LL i=1;i<=n;i++) scanf("%lld%lld",&A[i],&B[i]); sort(A+1,A+1+n); sort(B+1,B+1+n); LL mid,ans; LL l=A[1]*B[1],r=A[n]*B[n]; while(l<=r) { mid=(l+r)>>1; if(check(mid)) ans=mid,l=mid+1; else r=mid-1; } printf("%lld",ans); return 0;}
51nod 1105 第K大的数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。