第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\)的范围。
南京师范大学算法赛队2021年7月集训程序设计竞赛(小兰集训赛)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 10
- 开始于
- 2021-07-16 13:30
- 结束于
- 2021-07-16 17:30
- 持续时间
- 4.0 小时
- 主持人
- 参赛人数
- 39