wordpress 视频站模板下载失败,建立网站做淘客,网站开发课程软件,免费软件下载网站有哪些会场安排问题 时间限制#xff1a;3000 ms | 内存限制#xff1a;65535 KB难度#xff1a;4描述学校的小礼堂每天都会有许多活动#xff0c;有时间这些活动的计划时间会发生冲突#xff0c;需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动#xff0c;… 会场安排问题 时间限制3000 ms | 内存限制65535 KB 难度4 描述学校的小礼堂每天都会有许多活动有时间这些活动的计划时间会发生冲突需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动每个时间最多安排一个活动。现在小刘有一些活动计划的时间表他想尽可能的安排更多的活动请问他该如何安排。 输入第一行是一个整型数m(m100)表示共有m组测试数据。 每组测试数据的第一行是一个整数n(1n10000)表示该测试数据共有n个活动。 随后的n行每行有两个正整数Bi,Ei(0Bi,Ei10000),分别表示第i个活动的起始与结束时间BiEi) 输出对于每一组输入输出最多能够安排的活动数量。 每组的输出占一行样例输入 2
2
1 10
10 11
3
1 10
10 11
11 20样例输出 1
2 提示 注意如果上一个活动在t时间结束下一个活动最早应该在t1时间开始 思想这里运用贪心算法先把结束的时间进行排序再比较开始的时间。 qsort和sort两种排序方法定义结构体输入开始时间和结束时间。 #includestdio.h
#includestdlib.h
#define N 10001
struct node
{int beg;int end;
}table[N];
int cmp(const void* a,const void* b)//对结束时间进行排序
{return (*(struct node *)a).end-(*(struct node *)b).end;
}
int main()
{int m;scanf(%d,m);while(m--){int n,i,j;scanf(%d,n);for(i0;in;i)scanf(%d%d,table[i].beg,table[i].end);//输入活动开始和结束时间qsort(table,n,sizeof(table[0]),cmp);int min-1,count0;for(i0;in;i){if(table[i].begmin){count;mintable[i].end;}} printf(%d\n,count);}return 0;
}此题主要利用时间安排表的贪心性质可以先对结束时间进行排序然后把第一个活动加入安排因为如果第一个活动不加进去的话后面的结束时间总是大于第一个活动的结束时间所以满足不了局部最优故加入第一个之后要做的就是比较开始时间和结束时间设起始时间Si和一个结束时间Fi且SiFi设活动i和j且初始化i1j0只要有SiFj就把活动i加入安排并使ji然后i递增直到in即可统计活动安排个数其中n数据在[0,10000)比较大所以要使用快速排序时间复杂度为nlog(n)具体代码如下 #includeiostream
#includestdio.h
#includealgorithm
using namespace std;
#define N 10001
struct A
{int beg;int end;
}table[N];
int cmp(A a,A b)
{return a.endb.end?1:0;
}
void Input(int m)
{int n,i,j;while(m--){scanf(%d,n);for(i0;in;i)scanf(%d%d,table[i].beg,table[i].end);//输入活动开始和结束时间sort(table,tablen,cmp);int num1;j0;for(i1;in;i){if(table[i].begtable[j].end){num;j i;}}printf(%d\n,num);}
}
int main()
{int m;scanf(%d,m);Input(m);return 0;
}
