huichang.cpp

对贪心算法的应用

#include<fstream.h>
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
/*
int Partition(int a[], int low, int high )//划分
{
	int i,j;
	int x = a[low];
	i = low;
	j = high;
	while(i<j)
	{
		while(i<j&&x < a[j])
		{
			j = j - 1;
		}
		if(i<j)
		{
			a[i] = a[j];
			i=i+1;
		}
		while(i<j&&x >= a[i])
		{
			i = i + 1;
		}
		if(i<j)
		{
			a[j] = a[i];
			j=j-1;
		}
	}
	a[i] = x;
	return i;
}

void QuickSort(int a[], int low, int high)
{
	int Position;
	if(low < high)
	{
		Position = Partition(a,low,high);
		QuickSort(a, low, Position-1);
		QuickSort(a, Position+1, high);
	}
}
*/
//交换函数
void swap1(int *a,int *b){
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}
//选择排序
void sort1(int *a,int b[],int as)
{
	int i,j,index;
    int elem;
	for(i=0;i<as-1;i++){
		elem=*(a+i);
		index=i;
		for(j=i+1;j<as;j++){
			if(*(a+j)<elem){
				elem=*(a+j);
				index=j;
			}
			else if((*(a+j)==elem) && (b[j]<b[i])){//开始时间相同，比较结束时间
				elem=*(a+j);
			    index=j;
			}
		}
				
			swap1(a+i,a+index);
			swap1(&b[i],&b[index]);
	}

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

void main( )
{
	ifstream fin("input.txt");
	ofstream fout("output.txt");
	int n;
	fin>>n;  //读入会场数
	int *st=new int[n];   //开始时间
	int *et=new int[n];   //结束时间
	for(int i=0;i<n;i++)
	{
		fin>>st[i]>>et[i];      //读入开始和结束时间
	}
	cout<<"排序前---------------"<<endl<<"开始时间"<<endl;
	for( i=0;i<n;i++)
		cout<<"　"<<st[i];
	cout<<endl<<"结束时间"<<endl;
	for( i=0;i<n;i++)
		cout<<"　"<<et[i];
	sort1(st,et,n);
	//QuickSort(st,0,n-1);
	//QuickSort(et,0,n-1);
	cout<<endl<<endl<<"排序后---------------"<<endl<<"开始时间"<<endl;
    for( i=0;i<n;i++)
		cout<<"　"<<st[i];
	cout<<endl<<"结束时间"<<endl;
	for( i=0;i<n;i++)
		cout<<"　"<<et[i];
	fout<< schedule(st,et,0,n-1) <<endl; //把所需会场数写入文件
	delete []st;
	delete []et;
	cout<<endl<<"--------------所需会场数是-----------------------"<<"\t"<<endl;
    ifstream fin1("output.txt");         
	fin1>>n;                             //将所需会场数读出
	cout<<n<<endl;
	fin.close();                          //关闭文件流
	fout.close();
	fin1.close();                   

}