1298 活动选择

朴灿烈づ我的快乐病毒、 2022-04-24 09:50 169阅读 0赞

### 活动选择 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

学校的大学生艺术中心周日将面向全校各个学院的学生社团开放，但活动中心同时只能供一个社团活动使用，并且每一个社团活动开始后都不能中断。现在各个社团都提交了他们使用该中心的活动计划（即活动的开始时刻和截止时刻）。请设计一个算法来找到一个最佳的分配序列，以能够在大学生艺术中心安排不冲突的尽可能多的社团活动。  
比如有5个活动，开始与截止时刻分别为：  
  
![1298.png][]  
  
最佳安排序列为：1,4,5。

Input

第一行输入活动数目ｎ（0<ｎ<100）；  
以后输入ｎ行，分别输入序号为1到ｎ的活动使用中心的开始时刻ａ与截止时刻ｂ（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

#include <bits/stdc++.h>
    using namespace std;
    
    struct node{
      int a,b,num;
    }s[110];
    
    bool cmp(struct node x,struct node y){
      return x.b<y.b;
    }
    
    int main()
    {
      int n,end;
      std::cin >> n;
      for(int i = 0; i < n; i++){
        std::cin >> s[i].a >> s[i].b;
        s[i].num = i+1;
      }
      sort(s,s+n,cmp);        //按照结束先后时间排序
      end = s[0].b;
      std::cout << s[0].num;
      for(int i = 1; i < n; i++){
        if(s[i].a>=end){
          end = s[i].b;
          std::cout << "," <<s[i].num;
        }
      }
      std::cout << '\n';
      return 0;
    }

[1298.png]: http://acm.sdut.edu.cn/image/1298.png

发表评论取消回复

表情：

评论列表（有 0 条评论，169人围观）

还没有评论，来说两句吧...

相关阅读

相关活动选择

欢迎访问我的个人博客：[苦酒的个人小站][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 赞/ 203 阅读

相关活动选择

活动选择 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 赞/ 170 阅读

相关活动选择

活动选择 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 学校的大学生艺术中心周日将面

墨蓝/ 2022年02月16日 14:18/ 0 赞/ 244 阅读