马航飞-6分.txt

这是很不错的计算机算法

#include <stdio.h>
#include  <iostream.h>
#include  <fstream.h>
#include <stdlib.h>
#include <time.h>
void swap(int *i,int *j)
	{
	  int k;
	  k=*i;
	  *i=*j;
	  *j=k;
	}

int partition(int a[],int p,int r)
	{
	  int i=p,
                  j=r+1;
	  int x=a[p];	  
	  while(1)
		  {
		  while (a[++i]<x);
		  while (a[--j]>x);
		  if(i>=j) break;			   
        swap(&a[i],&a[j]);			  
          }
	  a[p]=a[j];	 
	  a[j]=x;	 
	  return j;
	}

void quicksort(int a[],int p,int r)
	{
	  if(p<r)
		  {
		               int q=partition(a,p,r);
			quicksort(a,p,q-1);
			quicksort(a,q+1,r);
		  }
	}

 int schedule(int a[],int b[],int p,int r)
	{
                  int n=0;
	  int i=p+1;
	  if (a[p]>-1) 
                        {		    
		n=1;
                                 for(;i<=r;i++)
	 	      if(a[i]>=b[p])    //有一个活动结束，新活动可在已空闲的会场进行。
		 	   p++;
		       else 
		     	   n++;       //要增开一会场	 			 
		  }	  
	  return n;
	}

int main( )
	{
	  int n;	 
                 ifstream fin("input.txt",ios::nocreate);
	  if(fin.fail())
		   {
	      	cerr<<"the input.txt is not exist!"<<endl;
	    	exit(-1);
		   }
                  ofstream out("output.txt");
	  fin>>n;	 
	  int *s= new int[n];
	  int *e=new int[n];
                  for(int i=0;i<n;i++)
                        fin>>s[i]>>e[i];      
                  quicksort(s,0,n-1);
	  quicksort(e,0,n-1);
	  out<< schedule(s,e,0,n-1)<<endl;
                  fin.close();
	  out.close();
	  delete []s;
	  delete []e;
	  return 0;
	}