活动选择 深藏阁楼爱情的钟 2023-06-13 11:13 43阅读 0赞 欢迎访问我的个人博客:[苦酒的个人小站][Link 1] # 题目描述 # Problem Description 学校的大学生艺术中心周日将面向全校各个学院的学生社团开放,但活动中心同时只能供一个社团活动使用,并且每一个社团活动开始后都不能中断。现在各个社团都提交了他们使用该中心的活动计划(即活动的开始时刻和截止时刻)。请设计一个算法来找到一个最佳的分配序列,以能够在大学生艺术中心安排不冲突的尽可能多的社团活动。 比如有5个活动,开始与截止时刻分别为: ![format_png][] 最佳安排序列为:1,4,5。 Input 第一行输入活动数目n(0<n<100); 以后输入n行,分别输入序号为1到n的活动使用中心的开始时刻a与截止时刻b(a,b为整数且0<=a,b<24,a,b输入以空格分隔)。 Output 输出最佳安排序列所包含的各个活动(按照活动被安排的次序,两个活动之间用逗号分隔)。 Sample Input 6 8 10 9 16 11 16 14 15 10 14 7 11 Sample Output 1,5,4 # 题目思路 # 刚看到这道题,还是有点懵逼的。 总结一下题目的大致意思:**给你N个活动,每个活动有对应的开始和结束以及编号,让你找一个最合适的方法,来使进行的活动最多。** 直接开一个结构体,里面包含每个活动的开始、结束、编号、时间区间,这里的时间区间主要是为了后面排序使用,对于结构体进行排序,依次遍历,输出结果。 # 题目代码 # #include <iostream> #include <algorithm> #include <stdio.h> using namespace std; struct node { int start;//定义每一个的开始时间 int finish;//定义每一个的结束时间 int id;//为每一个活动赋予其相应的id int section;//定义每一个活动的区间范围,也就是执行活动的时间大小 } st[1222]; int cmp(node a, node b) { if(a.finish == b.finish) { return a.section < b.section;//如果结束时间相同的话,则根据区间的大小进行排序。 } else { return a.finish < b.finish;//根据结束时间进行升序排序 } } int main() { int n; cin>>n; for(int i = 1; i <= n; i++) { cin>>st[i].start>>st[i].finish; st[i].id = i; st[i].section = st[i].finish - st[i].start; } sort(st + 1,st + n + 1,cmp);//对当前的结构体按照结束的时间进行排序,如果结束的时间相等的话,则根据区间排序。 printf("%d", st[1].id);//排序完之后,选取第一个肯定是最优的。 int x = st[1].finish; for(int i = 2; i <= n; i++) { if(st[i].start >= x) { printf(",%d", st[i].id); x = st[i].finish; } } printf("\n"); return 0; } /*************************************************** User name: jk170631黄良帅 Result: Accepted Take time: 0ms Take Memory: 200KB Submit time: 2019-11-16 17:04:54 ****************************************************/ [Link 1]: https://www.huangliangshuai.com/2019/11/16/%E7%AE%97%E6%B3%95/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/%E6%B4%BB%E5%8A%A8%E9%80%89%E6%8B%A9/ [format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hY20uc2R1dC5lZHUuY24vaW1hZ2UvMTI5OC5wbmc?x-oss-process=image/format,png
相关 活动选择 欢迎访问我的个人博客:[苦酒的个人小站][Link 1] 题目描述 Problem Description 学校的大学生艺术中心周日将面向全校各个学院的学生社团开放 深藏阁楼爱情的钟/ 2023年06月13日 11:13/ 0 赞/ 44 阅读
相关 活动选择问题 Problem Description sdut 大学生艺术中心每天都有n个活动申请举办,但是为了举办更多的活动,必须要放弃一些活动,求出每天最多能举办多少活动。 Inpu 叁歲伎倆/ 2022年07月13日 04:52/ 0 赞/ 190 阅读
相关 活动选择 Problem Description 学校的大学生艺术中心周日将面向全校各个学院的学生社团开放,但活动中心同时只能供一个社团活动使用,并且每一个社团活动开始后都不能中断。现 电玩女神/ 2022年07月13日 03:49/ 0 赞/ 196 阅读
相关 活动选择 活动选择 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Pro 青旅半醒/ 2022年07月12日 01:30/ 0 赞/ 189 阅读
相关 贪心——活动选择 活动选择 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description ゝ一纸荒年。/ 2022年07月11日 01:41/ 0 赞/ 202 阅读
相关 活动选择 活动选择 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statistic][S 怼烎@/ 2022年06月17日 09:49/ 0 赞/ 174 阅读
相关 活动选择 活动选择 Problem Description 学校的大学生艺术中心周日将面向全校各个学院的学生社团开放,但活动中心同时只能供一个社团活动使用,并且每一个社团活动开始后 亦凉/ 2022年05月16日 13:11/ 0 赞/ 170 阅读
相关 活动选择 活动选择 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description 女爷i/ 2022年05月16日 13:09/ 0 赞/ 205 阅读
相关 1298 活动选择 活动选择 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 学校的大学生艺术中心周日将面 朴灿烈づ我的快乐病毒、/ 2022年04月24日 09:50/ 0 赞/ 169 阅读
相关 活动选择 活动选择 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 学校的大学生艺术中心周日将面 墨蓝/ 2022年02月16日 14:18/ 0 赞/ 244 阅读
还没有评论,来说两句吧...