Differences

This shows you the differences between two versions of the page.

--- exam3 [2012/04/14 09:26] – [2108] xcyan
+++ exam3 [2012/04/14 12:56] (current) – [2108] xcyan
@@ Line 42: / Line 42: @@
 两个有序队列做合并，数据结构课里面应该讲过怎么做吧。现在我们将N扩大，然后就是N个有序队列做合并。
+"配对I" 这个题有2种做法 by 蒋舜宁：
+  - N路归并。先将A,B排序，考虑A[i]+B[j], j=1..N这个数列，对于每一个i都有一个N个数的有序数列，我们选取当前剩下的序列头中最小的那个，自然就是当前最小的一对。然后这就成了一个N路归并的问题。如果没法一下子想清楚，就画个图试试看吧，N行，每行N个数，每次比较这N行的头，然后把选了的那个头划掉，划N次。
+  - 二分答案套二分查找。我们发现，我们可以把第N大的数找出来。事实上，如果我们知道了一个数T，就可以算出比他小的有多少个，这个通过排序A,B，枚举每个i，然后二分得到B[j]<=T-A[i]的个数，再加起来，就可以搞出来，这一步的复杂度是kNlogN，k是个常数(<32)。最后，我们可以用算出来的答案ret，还原最后一次二分：再枚举i=1到N，将所有A[i]+B[j]<=ret的扔进数组，排序输出即可。
+上述两种方法都可以通过此题。