题目：

给定一个未排序的数组(x1, x2, … ,xn)，其中每个元素关联一个权值：(w1, w2, … ,wn)，且。请设计一个线性时间的算法，在该数组中查找其带权中位数xk，满足：

在这里插入图片描述

算法思想：

线性时间算法即为O（n），联想到之前写过的Select过程中的partition，选定一个pivot，将数组分成小于基数与大于基数的两部分，再计算两部分的权重和，如果左边的权重和大于右边的权重和，那么说明带权中位数在左边，对左边进行递归寻找，若左边权重和小于右边权重和，那么就说明，带权中位数在右边对右边进行递归寻找。

代码：

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
struct Node
{
    int value;
    double weight;
};
int partition(vector<Node>&A, int p, int r)
{
    int less = p - 1, i;
    int pivot = p + rand() % (r - p + 1);
    for (i = p; i <= r; i++)
    {
        if (A[i].value < A[pivot].value)
        {
            less++;
            swap(A[less], A[i]);
        }
    }
    swap(A[less + 1], A[pivot]);
    return less + 1;
}
int WeightedMedian(vector<Node>&A, int p, int r)
{
    if (p == r)
        return A[p].value;
    if (r - p == 1)
    {
        if (A[p].weight == A[r].weight)
            return (A[p].value + A[r].value) / 2;
        if (A[p].weight > A[r].weight)
            return A[p].value;
        else
            return A[r].value;
    }
    int q = partition(A, p, r);
    double wl = 0, wr = 0;
    for (int i = p; i <= q - 1; i++)
    {
        wl += A[i].weight;
    }
    for (int i = q + 1; i <= r; i++)
    {
        wr += A[i].weight;
    }
    if (wr < 0.5&&wl < 0.5)
        return A[q].value;
    else
    {
        if (wl > wr)
        {
            A[q].weight += wr;
            WeightedMedian(A, p, q);
        }
        else
        {
            A[q].weight += wl;
            WeightedMedian(A, q, r);
        }
    }
}
void Print(vector<Node>A)
{
    for (int i = 0; i < A.size(); i++)
        cout << A[i].value << " ";
    cout << endl;
    for (int i = 0; i < A.size(); i++)
        cout <</*setprecision(2)<< */A[i].weight<<" ";
    cout << endl;
}
void Initial(vector<int>&B,int n)
{
    for (int i = 0; i < n; i++)
    {
        B.push_back(0);
    }
}
int main(void)
{
    int n, sum = 0;
    cin >> n;
    vector<Node>A;
    vector<int>B;
    A.resize(n);
    B.resize(n);
    Initial(B,n);
    for (int i = 0; i < n; i++)
    {
        A[i].value = rand() % 100;
        do { B[i] = rand() % 100; } while (B[i] == 0);
        sum += B[i];
    }
    for (int i = 0; i < n; i++)
    {
        A[i].weight = (double)B[i] / sum;
    }
    Print(A);
    cout << WeightedMedian(A, 0, n - 1);
    system("pause");
    return 0;
}