URAL 1306

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

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

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

 1 #include<bits/stdc++.h>
 2 #define eps 1e-9
 3 #define FOR(i,j,k) for(int i=j;i<=k;i++)
 4 #define MAXN 1005
 5 #define MAXM 40005
 6 #define INF 0x3fffffff
 7 using namespace std;
 8 typedef long long LL;
 9 int main()
10 {
11     int n,m,t,i;
12     scanf("%d",&n); m=n/2+1;
13     priority_queue <int> q;//定义优先队列
14     for (i=1;i<=m;i++)//先读入n/2+1个数，直接加入优先队列
15     {
16          scanf("%d",&t);
17          q.push(t);
18     }
19     for (i=m+1;i<=n;i++)//读入其他数
20     {
21         scanf("%d",&t);
22         if (t<q.top())//如果小于最大值，就把最大值挤掉，然后把它加进优先队列
23         {
24             q.push(t);
25             q.pop();
26         }
27     }
28     if (n%2) printf("%d
",q.top());//n是奇数，优先队列最大值就是中位数
29     else//否则是前两大的数的平均值
30     {
31         LL sum=q.top();
32         q.pop();
33         sum+=q.top();
34         if (sum%2) printf("%I64d.5
",sum/2);
35         else printf("%I64d
",sum/2);
36     }
37     return 0;
38 }