第k小的乘积
第\(k\)小的乘积
时间限制:1s
空间限制:64MB
题目描述
给定长度为\(n\)的正项数列\(a,b\),在\(a,b\)两个数列中各取一个数\(a_i,b_j\)并将它们相乘,可以得到一个乘积。问\(a_i*b_j\)这共\(n^2\)个乘积中,第\(k\)小的数是多少?
输入格式
第一行两个整数\(n,k\),表示数列长度和要查询的排名\((第k小)\)。。
接下来两行每行\(n\)个整数,表示\(a,b\)两个正项数列。
输出格式
一个整数,表示答案。
样例输入1
2 2
1 2
5 4
样例输出1
5
样例1解释
四个乘积分别为: 5 4 10 8
最小的是4,第二小的是5,所以答案填5
样例输入2
3 2
1 1 1
2 4 10
样例输出2
2
样例2解释
乘积按大小排名分别是:2,2,2,4,4,4,10,10,10
排在第二位的是2
样例输入3
10 12
2 5 12 2 45 6 23 4 5 8
6 1 23 5 21 27 32 11 4 3
样例输出3
10
数据范围及限制
\(1\le n\le 10^5,1\le k\le n^2,1\le a_i,b_i\le 10^9\)
请注意:两个数的乘积可能超出\(int\)的范围。
信息
- ID
- 1263
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 32
- 已通过
- 2
- 通过率
- 6%
- 被复制
- 5
- 上传者
相关
在下列比赛中: