Weighted Median

For n elements x1, x2, ..., xn with positive integer weights w1, w2, ..., wn. The weighted median is the element xk satisfying
Weighted Median-LMLPHP

and

, S indicates Weighted Median-LMLPHP

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

Hint

The S which indicates the sum of all weights may be exceed a 32-bit integer. If S is 5, Weighted Median-LMLPHP

equals 2.5.

这是一道山东省省赛的题，英语不好的我看了以后一脸懵逼，最后花了好长时间才看懂，原来很是简单

题目意思：
给一些数x和它们对应的权值w，按照如图所示公式，s是所有权值w的总和。
求一个xk，使得满足前两个公式。

解题思路：
用结构体保存元素值和权值，先升序排列，累计xk之前的权值和，直到该权值大于s。

#include<stdio.h>

#include<algorithm>

using namespace std;

struct message{

int x;

int w;

}a[10000010];

int my_cmp(message a,message b)

{

    if(a.x<b.x)

        return 1;

    else

        return 0;

}

int main()

{

    int n,i;

    double s,y;

    while(scanf("%d",&n)!=EOF)

    {

        s=0;

        for(i=0;i<n;i++)

        scanf("%d",&a[i].x);

        for(i=0;i<n;i++)

        {

            scanf("%d",&a[i].w);

            s=s+a[i].w;

        }

        s=s/2.0;

        y=0;

        sort(a,a+n,my_cmp);

        for(i=0;i<n;i++)

        {

            y=y+a[i].w;

            if(y>s)

            {

                printf("%d\n",a[i].x);

                break;

            }

        }

    }

    return 0;

}

xK

Weighted Median