首页 > 代码库 > poj 2623 Sequence Median 堆的灵活运用
poj 2623 Sequence Median 堆的灵活运用
I - Sequence Median
Time Limit:1000MS Memory Limit:1024KB 64bit IO Format:%I64d & %I64uDescription
Given a sequence of N nonnegative integers. Let‘s define the median of such sequence. If N is odd the median is the element with stands in the middle of the sequence after it is sorted. One may notice that in this case the median has position ( N+1)/2 in sorted sequence if sequence elements are numbered starting with 1. If N is even then the median is the semi-sum of the two "middle" elements of sorted sequence. I.e. semi-sum of the elements in positions N/2 and ( N/2)+1 of sorted sequence. But original sequence might be unsorted.
Your task is to write program to find the median of given sequence.
Input
The first line of input contains the only integer number N — the length of the sequence. Sequence itself follows in subsequent lines, one number in a line. The length of the sequence lies in the range from 1 to 250000. Each element of the sequence is a positive integer not greater than 2 31−1 inclusive.
Output
You should print the value of the median with exactly one digit after decimal point.
Sample Input
| input | output |
|---|---|
43645 | 4.5 |
这道题 你会发现存不下，只能存一半
然后瞎搞搞，就出来了
#include <cstdio>#include <cmath>#include <cstring>#include <ctime>#include <iostream>#include <algorithm>#include <set>#include <vector>#include <sstream>#include <queue>#include <typeinfo>#include <fstream>typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 100001const int inf=0x7fffffff; //无限大priority_queue<unsigned int> q;int main(){ int n; while(cin>>n) { while(!q.empty()) q.pop(); unsigned int x; int kill=n/2+1; unsigned int fuck; for(int i=0;i<kill;i++) { cin>>x; q.push(x); } for(int i=kill;i<n;i++) { cin>>x; fuck=q.top(); if(x<fuck) { q.pop(); q.push(x); } } if(n%2==0) { unsigned int a=q.top(); q.pop(); unsigned int b=q.top(); printf("%.1lf\n",(a+b)/2.0); } else { unsigned int a=q.top(); printf("%.1lf\n",a*1.0); } } return 0;}
poj 2623 Sequence Median 堆的灵活运用
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。