URAL 1306 – Sequence Median 小内存求中位数

【题意】给出n（1~250000）个数（int以内），求中位数

【题解】一开始直接sort，发现MLE，才发现内存限制1024k，那么就不能开int[250000]的数组了（4*250000=1,000,000大约就是1M内存）。

后来发现可以使用长度为n/2+1的优先队列，即包含前一半的数以及中位数，其他数在读入的时候就剔除，这样可以省一半的空间。

 #include<bits/stdc++.h>
 #define eps 1e-9
 #define FOR(i,j,k) for(int i=j;i<=k;i++)
 #define MAXN 1005
 #define MAXM 40005
 #define INF 0x3fffffff
 using namespace std;
 typedef long long LL;
 int main()
 {
     int n,m,t,i;
     scanf("%d",&n); m=n/+;
     priority_queue <int> q;//定义优先队列
     for (i=;i<=m;i++)//先读入n/2+1个数，直接加入优先队列
     {
          scanf("%d",&t);
          q.push(t);
     }
     for (i=m+;i<=n;i++)//读入其他数
     {
         scanf("%d",&t);
         if (t<q.top())//如果小于最大值，就把最大值挤掉，然后把它加进优先队列
         {
             q.push(t);
             q.pop();
         }
     }
     if (n%) printf("%d\n",q.top());//n是奇数，优先队列最大值就是中位数
     else//否则是前两大的数的平均值
     {
         LL sum=q.top();
         q.pop();
         sum+=q.top();
         if (sum%) printf("%I64d.5\n",sum/);
         else printf("%I64d\n",sum/);
     }
     return ;
 }