求C++语言解答（oj题目）

分治法求n个元素的带权中位数
Description

某一个班级包括m个同学，某次考试结束后，统计发现，同学们的分数分布于n个不同的正整数值x1, x2, x3, ...xn无序放在数组中。每个分数值都有一个权值（为正数），代表取得该分数值的同学的人数百分比，所有权值的和为1。

现想统计同学们分数的带权中位数，带权中位数的定义为：

若存在分数值xk满足：所有小于xk的元素的权重和≤0.5，且所有大于xk的元素的权重和≤0.5，则称分数值xk为x1, x2, x3, ...xn的带权中位数。

请计算同学们成绩的带权中位数

值得注意的是，在本题中，我们只需关心小于/大于某个数的数是哪些、它们的权重和满不满足要求，而对这些数内部的准确排序情况并不关心。而快速排序在每一次划分之后，pivot左侧的数一定都比pivot小，右侧的数一定都比pivot大。因此借鉴快速排序的划分思路可以更加快速地找出带权中位数，而不需要对整个数组进行完整的排序。并且，在每次划分之后，（子）数组会被分成两半，其中一半的内部排序情况将不再重要，因此，每次划分只需选取另一半进行递归排序即可。

要求借鉴快速排序的划分思路对数组进行升序排序，找出n个元素的带权中位数，并且输出得出该带权中位数时，数组A的当前值。

在每次快速排序的划分时，选择子数组的第一个元素作为pivot。

Input

输入共有三行：

第一行：分数值的个数n

第二行：存储n个分数值的无序序列数组A，数组元素之间用空格分隔

第三行：n个分数值各自对应的权重数组B，数组元素之间用空格分隔

Output

要求输出为两行：

第一行：n个元素的带权中位数的值

第二行：计算得出该中位数时，数组A的当前值，数组元素之间用空格分隔