请教下POJ的2623,总是超时啊??

来源:百度知道 编辑:UC知道 时间:2024/05/12 08:03:46
#include<iostream>
using namespace std;

long partition(unsigned long s[],long p,long r)
{
long i,j;
unsigned long x,t;
x=s[r];
i=p-1;
for(j=p;j<r;j++)
if(s[j]<=x)
{
i++;
t=s[i];
s[i]=s[j];
s[j]=t;

}
t=s[i+1];
s[i+1]=s[r];
s[r]=t;
return (i+1);
}

unsigned long nth_element(unsigned long *data,long left,long right,long n)
{
long k=n-1;
if(left>right)
return -1;
while(1)
{
int i=partition(data,left,right);
if(k<i)
right=i-1;
else if(k>i)
left=i+1;
else
return data[i];
}
}

int main()
{
long n;
unsigned long a[250002];
cin>>n;
for(long i=0;i<n;i++)
cin>>a[i];
if(n&1)
cout<<nth_element(a,0,n-1,n/2+1)<<".0"<<endl;
else

估计有特殊的数据,专门卡你的非随机化算法
你试试看这组数据会不会超时
250000
1
2
3
...(省略249996行)
250000

把你的partition随机化就可以了
具体做法是,首先取一个随机数q,并且p<=q<=r
然后交换s[q]和s[r]
然后接着你的x=s[r]...就可以了
也就是在partition的时候用一个随机的元素而不总是s[r]来进行分隔
这样就不会被有序的数组卡掉了