山东省第五届ACM大学生程序设计竞赛-Weighted Median（模拟）

快来打我* 2022-08-21 06:50 169阅读 0赞

## Weighted Median ##

#### Time Limit: 2000MS Memory limit: 65536K ####

## 题目描述 ##

For n elements x1, x2, ..., xn with positive integer weights w1, w2, ..., wn. The weighted median is the element xk satisfying  
![2886_1.png][] and ![2886_2.png][] , S indicates ![2886_3.png][]

Can you compute the weighted median in O(n) worst-case?

## 输入 ##

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).

## 输出 ##

One line for each case, print a single integer number— the weighted median of the sequence.

## 示例输入 ##

7
    10 35 5 10 15 5 20
    10 35 5 10 15 5 20

## 示例输出 ##

## 提示 ##

The S which indicates the sum of all weights may be exceed a 32-bit integer. If S is 5, ![2886_4.png][] equals 2.5.

## 来源 ##

2014年山东省第五届ACM大学生程序设计竞赛  
  
题目意思：  
给一些数x和它们对应的权值w，按照如图所示公式，s是所有权值w的总和。  
求一个xk，使得满足前两个公式。  
  
解题思路：  
用结构体保存元素值和权值，先升序排列，累计xk之前的权值和，直到该权值大于s。

/* 
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院 
    * All rights reserved. 
    * 文件名称：s.cpp 
    * 作    者：单昕昕 
    * 完成日期：2016年4月20日 
    * 版 本 号：v1.0 
    */
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N=100000010;
    struct Node
    {
        int x,w;
    } node[N];
    
    int cmp(Node a,Node b)//结构体排序
    {
        return a.x<b.x;
    }
    
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            int i;
            double sum=0;//注意用double
            for(i=0; i<n; i++)
                scanf("%d",&node[i].x);
            for(i=0; i<n; i++)
            {
                scanf("%d",&node[i].w);
                sum+=node[i].w;
            }
            sum/=2.0;
            double s=0;
            sort(node,node+n,cmp);//升序
            for(i=0; i<n; ++i)
            {
                s+=node[i].w;
                if(s>sum)
                {
                    printf("%d\n",node[i].x);
                    break;
                }
            }
        }
        return 0;
    }

[2886_1.png]: http://acm.sdut.edu.cn/image/2886_1.png
[2886_2.png]: http://acm.sdut.edu.cn/image/2886_2.png
[2886_3.png]: /images/20220724/527d2a84b4b8475ba5e880127a09e2cf.png
[2886_4.png]: /images/20220724/8845c810d3214470915fde7db971c253.png