Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1445,我NlongN的算法为什么还会超时,哪位大虾帮忙看看程序,不胜感激

Posted by 4404124 at 2007-04-10 08:26:07 on Problem 1456
1445,我NlongN的算法为什么还会超时,哪位大虾帮帮看看程序
#include<iostream.h>
#define	MAX 10001
void saixuan(int b[MAX],int a[MAX],int s,int m)
{int t,r,i;
 t=b[s];r=a[s];
   for(i=2*s;i<m+1;i=i*2)
	{if(i<m)
	    if(b[i]<b[i+1]||(b[i]==b[i+1]&&a[i]>a[i+1]))
		   i++; 
	  if(t>=b[i])
	  { if(t>b[i]) 
		  break;
	    else
		   if(r>a[i])
           {b[s]=b[i];
	        a[s]=a[i];
	        s=i;
		   }
		   else
			  break;
	  }
	  b[s]=b[i];
	  a[s]=a[i];
	  s=i;	  
   }
	b[s]=t;
	a[s]=r;
}
   
void heapsort(int b[MAX],int a[MAX],int n)
{int k;
 void saixuan(int b[MAX],int a[MAX],int s,int m);
    for(int i=n/2;i>0;i--)
	  saixuan(b,a,i,n);
	    for(int j=n;j>1;j--)
	   {k=b[1];b[1]=b[j];b[j]=k;
		k=a[1];a[1]=a[j];a[j]=k;
		saixuan(b,a,1,j-1);
	   }
}

void main()
{int b[MAX],a[MAX],count,n,i;
 long int max;
   while(1)
   { max=0;
	 count=0;
     cin>>n;
	   for(i=1;i<n+1;i++)
		  cin>>a[i]>>b[i];
	      heapsort(b,a,n);
			     for(i=1;i<n+1;i++)
				    if(count<b[i])
                    {count=count+1;
					 max=max+a[i];
					}
				 cout<<max<<endl;
   }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator