首页 > 代码库 > CODEVS 2610活动选择

CODEVS 2610活动选择

2024-09-20 00:01:48   216人阅读

2610 活动选择

题目描述 Description

假设有一个需要使用某一资源的n（n≤1000）个活动组成的集合S，S={1，…，n}。该资源一次只能被一个活动占有，每一个活动有一个开始时间bi和结束时间ei（bi≤ei）。若bi>ej或者bj>ei，则活动i和活动j兼容。

你的任务是是：选择由互相兼容的活动组成的最大集合。

输入描述 Input Description

共n+1行，其中第1行为n，第2行到第n+1行表示n个活动的开始时间和结束时间（中间用一个空格隔开），格式为：

n

b1  e1

…….

bn  en

输出描述 Output Description

共有两行，第1行为满足要求的活动占用的时间t，第2行为最大集合中的活动序号，每个序号之间用一个空格隔开。

样例输入 Sample Input

11

3 5

1 4

12 14

8 12

0 6

8 11

6 10

5 7

3 8

5 9

2 13

样例输出 Sample Output

14

2 3 6 8

数据范围及提示 Data Size & Hint

数据范围不大，不用考虑。

 

这道题是个大坑，除非打表，否则不可能通过，因为测试数据粘上了其他题目的数据

正解：

 1 #include <cstdio>
 2 #include<iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N=1e5+6;
 6 struct activity{
 7     int start,end;//开始，结束时间 
 8     int xh;//记录序号 
 9 }a[N];
10 int n,ans;
11 int act[1001];//记录选择的活动序号 
12 int cmp(const activity &a,const activity &b)
13 {
14     return a.end<b.end;
15 }
16 int main()
17 {
18     cin>>n;
19     for(int i=1;i<=n;i++)
20     {
21         cin>>a[i].start>>a[i].end;
22         a[i].xh=i;
23     }
24     sort(a+1,a+n+1,cmp);//按结束时间进行从小到大排序 
25     int cur=0,tot=0;
26     for(int i=1;i<=n;i++)
27         if(a[i].start>cur)//选择结束时间早的活动 
28         {
29             cur=a[i].end;
30             ans+=a[i].end-a[i].start+1;
31             act[++tot]=a[i].xh;
32         }
33     cout<<ans<<endl;
34     sort(act+1,act+tot+1);
35     for(int i=1;i<=tot;i++)
36         cout<<act[i]<<" ";
37     return 0;
38 }

 

CODEVS 2610活动选择


联系
我们