Weighted Median
Time Limit: 2000 ms
Memory Limit: 65536 KiB
Problem Description
For n elements x1, x2, ..., xn with positive integer weights w1, w2, ..., wn. The weighted median is the element xk satisfying
and 
, S indicates 
and , S indicates Can you compute the weighted median in O(n) worst-case?
Input
There are several test cases. For each case, the first line contains one integer n(1 ≤ n ≤ 10^7) — the number of elements in the sequence. The following line contains n integer numbers xi (0 ≤ xi ≤ 10^9). The last line contains n integer numbers wi (0 < wi < 10^9).
Output
One line for each case, print a single integer number— the weighted median of the sequence.
Sample Input
7 10 35 5 10 15 5 20 10 35 5 10 15 5 20
Sample Output
20
Hint
The S which indicates the sum of all weights may be exceed a 32-bit integer. If S is 5, 
equals 2.5.
equals 2.5. Source
2014年山东省第五届ACM大学生程序设计竞赛