| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
总是超时.大牛看看这个可以改进吗?#include "iostream.h"
#include "stdio.h"
int temp[50000][2];
int total=0;
void Sort(int index,int len);
void main()
{
while(cin>>total)
{
if(total==0)
break;
for(int i=0;i<total;i++)
{
scanf("%d%d",&temp[i][0],&temp[i][1]);
}
Sort(0,total);
int X_max=0;
int num=0;
for(i=total-1;i>=0;i--)
{
if(temp[i][0]>X_max)
{
X_max=temp[i][0];
num++;
}
}
cout<<num<<endl;
}
}
void Sort(int index,int len)
{
if(len==1)
return;
int p=index;
int or=index;
int i=0;
for(i=index;i<index+len;i++)
{
if(temp[i][1]<temp[or][1])
{
int t=temp[p][1];
int t0=temp[p][0];
temp[p][1]=temp[i][1];
temp[p][0]=temp[i][0];
temp[i][1]=t;
temp[i][0]=t0;
if(or==p)
or=i;
p++;
}
}
if(or!=p)
{
int t=temp[or][1];
int t0=temp[or][0];
temp[or][1]=temp[p][1];
temp[or][0]=temp[p][0];
temp[p][1]=t;
temp[p][0]=t0;
}
if(p!=index)
{
Sort(index,p-index);
}
if(p!=(index+len-1))
{
Sort(p+1,index+len-p-1);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator