http://acm.jlu.edu.cn/joj/showproblem.php?pid=2576&contestid=131。
M*N个数,每个数的范围是>-10^8 并且 小于 10^8。
第K小的数,也必然会在这个范围内。
假如 a 是 第 k+1小的数。 那么第K小的数必然<a.
同样 如果 a 是 第K-1小的数。 那么第K小的数必然 >a.
这里,我们可以想象到 二分 枚举 第K小的数。(假如枚举的这个数是a。)
然后在C中查找 比 a 小的数的个数(假如为b)。
这样通过判断a和b的关系。可以使枚举的区间不断缩小。最终找到第K小的数。
剩下的问题就是怎么快速的找到比a小的数的个数。
把数组A排序。
B[i]*A得到的一行也一定是单调的。这样就可以二分找到这一行中比a小的数的个数。B数组的每一行都查找一次。
最后总的复杂度是
0(lg(10^8)*m*lgn)
M*N个数,每个数的范围是>-10^8 并且 小于 10^8。
第K小的数,也必然会在这个范围内。
假如 a 是 第 k+1小的数。 那么第K小的数必然<a.
同样 如果 a 是 第K-1小的数。 那么第K小的数必然 >a.
这里,我们可以想象到 二分 枚举 第K小的数。(假如枚举的这个数是a。)
然后在C中查找 比 a 小的数的个数(假如为b)。
这样通过判断a和b的关系。可以使枚举的区间不断缩小。最终找到第K小的数。
剩下的问题就是怎么快速的找到比a小的数的个数。
把数组A排序。
B[i]*A得到的一行也一定是单调的。这样就可以二分找到这一行中比a小的数的个数。B数组的每一行都查找一次。
最后总的复杂度是
0(lg(10^8)*m*lgn)