http://acm.timus.ru/problem.aspx?space=1&num=1306堆的優(yōu)先級(jí)序列：尋找中位數(shù),這個(gè)問題250000個(gè)數(shù)，如果排序nlogn,肯定不會(huì)超時(shí)，不過這里內(nèi)存只有1024K，最多也就只能保存25000個(gè)int，而且堆調(diào)用顯然會(huì)TLE，所以得尋找另外的辦法。堆，這里可以借用它的優(yōu)先級(jí)序列。因?yàn)橹挥脤ふ抑形粩?shù)，則保留前面一半或者后面一半都行，應(yīng)該分別使用大堆和小堆。這里我用的是大堆。開辟130000的數(shù)組，先讀入n/2+1個(gè)數(shù)，建堆。則最前面的數(shù)肯定是當(dāng)前最大的數(shù)。以后讀入的數(shù)如果比這個(gè)大或者等于，那么肯定排序應(yīng)該在后面一半，如果小，則當(dāng)前最大的數(shù)肯定是后面一半的，替換之，并且維護(hù)好這個(gè)堆。這個(gè)問題也在nlogn的時(shí)間內(nèi)解決的，也不會(huì)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;
}