http://acm.timus.ru/problem.aspx?space=1&num=1306堆的优先级序列：寻找中位数,这个问题250000个数，如果排序nlogn,肯定不会超时，不过这里内存只有1024K，最多也就只能保存25000个int，而且堆调用显然会TLE，所以得寻找另外的办法。堆，这里可以借用它的优先级序列。因为只用寻找中位数，则保留前面一半或者后面一半都行，应该分别使用大堆和小堆。这里我用的是大堆。开辟130000的数组，先读入n/2+1个数，建堆。则最前面的数肯定是当前最大的数。以后读入的数如果比这个大或者等于，那么肯定排序应该在后面一半，如果小，则当前最大的数肯定是后面一半的，替换之，并且维护好这个堆。这个问题也在nlogn的时间内解决的，也不会TLE：
#include<stdio.h>
#include<string.h>
#include<math.h>
int heap[130000];
int heapify(int i) //过滤下去
{
int n,l,r,large,tmp;
n=heap[0];
l=2*i;r=l+1;
if (l<=n&&heap[l]>heap[i])
large=l;
else
large=i;
if (r<=n&&heap[r]>heap[large])
large=r;
if (large!=i)
{
tmp=heap[i];heap[i]=heap[large];heap[large]=tmp;
heapify(large);
}
}
int main()
{
int n,i,t,max;
double ans;
while (scanf("%d",&n)==1)
{
t=n/2+1;
for (i=1;i<=t;i++)
scanf("%d",&heap[i]);
heap[0]=t;
for (i=t/2;i>=1;i--)
heapify(i);
for (i=t+1;i<=n;i++)
{
scanf("%d",&t);
if (t<heap[1])
{
heap[1]=t;
heapify(1);
}
}
if (n%2==1)
ans=heap[1]*2.0;
else
{
max=heap[2]>heap[3]?heap[2]:heap[3];
ans=heap[1]+max*1.0;
}
printf("%.1lf\n",ans/2.0);
}
return 0;
}