河北大学程序设计训练营

[TOC]

day10 Swan学院社团招新

Swan学院社团招新，招新宣讲会分散在不同时间段，大一新生小花花想知道自己最多能完整的参加多少个招新宣讲会(参加一个招新宣讲会的时候不能中断或离开)。
【问题说明】这个问题是对几个相互竞争的招新宣讲会活动进行调度，它们都要求以独占的方式使用某一公共资源（小花花）。调度的目标是找出一个最大的相互兼容的活动集合。 活动选择问题就是要选择出一个由互相兼容的问题组成的最大子集合。
【温馨提示】应先将所有的活动按照结束时间升序排列，然后再选择可能的时间组合，并求出最大的组合数，使用qsort()排序函数是一个不错的选择。
qsort 的函数原型是： void qsort(voidbase,size_t num,size_t width,int(__cdeclcompare)(const void,const void)); 功 能: 使用快速排序例程进行排序；头文件:stdlib.h； 参数: 1 待排序数组首地址；2 数组中待排序元素数量；3 各元素的占用空间大小；4 指向函数的指针，用于确定排序的顺序

输入格式:

第一行为n，表示有n个招新宣讲会，接下来n行每行两个整数表示开始时间和结束时间，由从招新会第一天0点开始的小时数表示（24小时制）。 n <= 1000 。

输出格式:

最多参加的招聘会个数。

输入样例:

1
2
3
4
3
9 10
10 20
8 15

输出样例:

1
2

本题是对贪心算法的理解。首先对活动的结束时间进行升序排序；然后依次比对后一项宣讲的开始时间与前一项宣讲的结束时间，如果后一项的开始时间晚于前一项的结束时间，则说明小花花可以参加后面一项的宣讲，以此类推遍历所有的时间。

  1. 题目对时间要求为1000ms，可以选择cin 和 cout，也可以用 scanf。如果时间要求短，则选择scanf或者ios::sync_with_stdio(false); //取消cin和stdin的同步。
  2. 注意结构体的用法。
  3. 在开数组的时候，多开十个，防止溢出。（尤其pta里）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<algorithm>
using namespace std;

struct person
{
    int startime;
    int endtime;
}a[1010];

//结束时间升序
bool cmp(person x,person y)
{
    return x.endtime < y.endtime;
}

int main()
{
    int n;
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0 ; i<n ; i++)
    {
        cin>>a[i].startime>>a[i].endtime;
    }
    sort(a,a+n,cmp);
    
    int count=1;//计数，可以参加的宣讲会数量
    int time=a[0].endtime;//记录第一个宣讲会结束的时间
    for(int i=1 ; i<=n ; i++)
    {
        if(a[i].startime>=time)
        {//下一个个宣讲会的开始时间大于当前记录的宣讲会的结束时间，则第二个宣讲会可以参加
            time=a[i].endtime;
            count++;
        }
    }
    cout<<count<<endl;
    return 0;
}

如果使用提示中的qsort函数，代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<algorithm>
using namespace std;

struct person
{
    int startime;
    int endtime;
}a[1010];

//结束时间升序
int cmp(const void* x,const void* y)
{
    struct person x1 = *(struct person*)x;
    struct person y1 = *(struct person*)y;
    return x1.endtime - y1.endtime;
}

int main()
{
    int n;
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0 ; i<n ; i++)
    {
        cin>>a[i].startime>>a[i].endtime;
    }
    qsort(a,n,sizeof(a[0]),cmp);
    
    int count=1;//计数，可以参加的宣讲会数量
    int time=a[0].endtime;//记录第一个宣讲会结束的时间
    for(int i=1 ; i<=n ; i++)
    {
        if(a[i].startime>=time)
        {//下一个个宣讲会的开始时间大于当前记录的宣讲会的结束时间，则第二个宣讲会可以参加
            time=a[i].endtime;
            count++;
        }
    }
    cout<<count<<endl;
    return 0;
}