首页 > 代码库 > [ACM] SDUT 2886 Weighted Median (省赛最悲剧的一道题)
[ACM] SDUT 2886 Weighted Median (省赛最悲剧的一道题)
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
and , S indicates
and , S indicates
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
示例输出
20
提示
The S which indicates the sum of all weights may be exceed a 32-bit integer. If S is 5, equals 2.5.
来源
2014年山东省第五届ACM大学生程序设计竞赛
当时最后半个多小时三个人死活没想出来怎么做,现在拿出这道题一看十几分钟就解决了。。。现场的时候心态实在是太重要了,一慌脑子就容易空白。。。
代码:
#include <iostream> #include <algorithm> #include <stdio.h> using namespace std; const int maxn=1e7+2; int n; struct Node { int x,w; }node[maxn]; bool cmp(Node a,Node b) { if(a.x<b.x) return true; return false; } int main() { while(scanf("%d",&n)!=EOF) { long long sum=0; for(int i=1;i<=n;i++) scanf("%d",&node[i].x); for(int i=1;i<=n;i++) { scanf("%d",&node[i].w); sum+=node[i].w; } long double S=sum*0.5; sort(node+1,node+1+n,cmp); long long xiao=0,da=0; int ans; for(int i=1;i<=n-1;i++) { xiao+=node[i].w; da=sum-xiao-node[i+1].w; if(xiao<S&&da<=S) { ans=node[i+1].x; break; } } cout<<ans<<endl; } return 0; }
[ACM] SDUT 2886 Weighted Median (省赛最悲剧的一道题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。