首页 > 代码库 > URAL 1306 Sequence Median（优先队列）

URAL 1306 Sequence Median（优先队列）

2024-07-15 15:50:51   223人阅读

题意：求一串数字里的中位数。内存为1M。每个数范围是0到2的31次方-1。

思路：很容易想到把数字全部读入，然后排序，但是会超内存。用计数排序但是数又太大。由于我们只需要第n/2、n/2+1大（n为偶数）或第（n+1）/2大（n为奇数）。所以可以用优先队列来维护最值，这样只需要存一半元素（n/2+1个元素）就可以了。

#include<cstdio>#include<algorithm>#include<queue>#define UL unsigned intusing namespace std;priority_queue<UL> que;int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        while(!que.empty()) que.pop();        {            UL a;            for(int i=0; i<=n/2; ++i)            {                scanf("%u",&a);                que.push(a);            }            for(int i=n/2+1; i<n; ++i)            {                scanf("%u",&a);                if(!que.empty()&&a<=que.top())                {                    que.pop();                    que.push(a);                }            }            if(n&1)                printf("%u",que.top());            else            {                UL a=que.top();                que.pop();                UL b=que.top();                printf("%.1f\n",(a+b)/2.0);            }        }    }    return 0;}
View Code

 


联系
我们