活动安排问题 贪心算法.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
using namespace std;

//活动安排问题 贪心算法
/*
输入：
11
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
输出：
4
0 3 7 10
*/
#define MAX 1000
int stime[15];
int otime[15];
int xulie[15];
int ok[15];

void init(int num)
{
	int i;
	for(i=0;i<num;i++) 
	{
		xulie[i]=i;
		ok[i]=0;
	}
}

void sort(int num)
{
	int i,j,tempmin,minnum,tt;
	for(i=0;i<num-1;i++)
	{
		tempmin=otime[i];
		minnum=i;
		for(j=i+1;j<num;j++)
		{
			if(tempmin>otime[j])
			{
				tempmin=otime[j];
				minnum=j;
			}
		}
		tt=otime[minnum];
		otime[minnum]=otime[i];
		otime[i]=tt;
		tt=xulie[minnum];
		xulie[minnum]=xulie[i];
		xulie[i]=tt;
	}
}

int cal(int num)
{
	int i,j=0,count=1;//i表示正在检测的活动，j表示刚刚检测过了的活动
	init(num);
	sort(num);
	ok[0]=1;
	for(i=1;i<num;i++)
	{
		if(stime[i]>=otime[j])
		{
			ok[i]=1;
			count++;
			j=i;
		}
		else
			ok[i]=0;
	}
	return count;
}


int main()
{
	int num,i;
	printf("输入活动的个数:");
	cin>>num;
	cout<<"输入各活动的开始时间";
	for(i=0;i<num;i++) cin>>stime[i];
	cout<<"输入各活动的结束时间";
	for(i=0;i<num;i++) cin>>otime[i];
	i=1;
	cout<<"被选择活动总个数为"<<cal(num);
	cout<<"\n分别是:";
	for(i=0;i<num;i++)
		if(ok[xulie[i]]) cout<<setw(3)<<xulie[i];
	return 0;
}