算法实验——用贪心思想设计实现活动安排问题.doc

用贪心思想设计实现活动安排问题
#include<ctime>
#include<iostream>
#include<cstdlib>
usingnamespacestd;
#defineMAX1000

voidGreedySelector(intn,floats[],floatf[],boolA[])
{
A[1]=true;
intj=1;
for(inti=2;i<=n;i++){
if(s[i]>=f[j]){A[i]=true;j=i;}
elseA[i]=false;
}
}

voidexchange(float&i,float&j)
{floatn;
n=i;
i=j;
j=n;
}

intpartition(floatb[],floata[],intp,intr)
{inti,j;
floatx;
x=a[r];
i=p-1;
for(j=p;j<=r-1;j++)
{if(a[j]<=x)
{i++;
exchange(a[i],a[j]);
exchange(b[i],b[j]);
}
}
exchange(a[i+1],a[r]);
exchange(b[i+1],b[r]);
return(i+1);

}

voidquicksort(floatb[],floata[],intp,intr)
{intm;
if(p<r)
{m=partition(b,a,p,r);
quicksort(b,a,p,m-1);
quicksort(b,a,m+1,r);
}
}

intmain(){
intk=0,key=1,i=1,j=1;
intn;
floatt1,t2;
floats[MAX],f[MAX];
boolA[MAX];
srand((unsigned)time(NULL));
clock_tstart1,end1,start2,end2;

while(k!=1&&k!=2)
{
printf("输入1：手动输入活动开始、结束时间\n输入2：随机生成活动开始、结束时间\n");
scanf("%d",&k);
if(k!=1&&k!=2)continue;
elseif(k==1)
{do{
printf("输入活动%d开始时间:",i);
scanf("%f",&t1);
s[i]=t1;
while(1){
printf("输入活动%d结束时间:",i);
scanf("%f",&t2);
if(t2>t1)break;
elseprintf("亲，别闹，好好输入\n");
}
f[i]=t2;
printf("输入1：继续添加活动\n输入0：结束添加\n");
scanf("%d",&key);
i++;
}while(key!=0);
n=--i;
printf("n=%d",n);
}//手动输入结束
elseif(k==2)
{printf("请输入活动个数n:\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
{f[i]=rand()%(24);
do{
s[i]=rand()%(24);
}while(s[i]>=f[i]);
}
}
}
quicksort(s,f,1,n);
start1=clock();
GreedySelector(n,s,f,A);
end1=clock();

printf("\n活动安排为：");
for(i=1,j=1;i<=n;i++)
{if(A[i])
{printf("\n活动%d:开始时间%f,结束时间%f",i,s[i],f[i]);
j++;
}
}
cout<<"\nProcessingTime:"<<end1-start1<<endl;
printf("\n");
system("pause");
}