hnust hold不住的老师

问题 H: Hold不住的老师

时间限制: 1 Sec 内存限制: 128 MB
提交: 415 解决: 63
[提交][状态][讨论版]

题目描述

因为我们学校ACM集训队取得的一个个优异成绩，ACM/ICPC越来越受到学校重视。学校为了提高大家的编程与算法能力，决定开设更多的上机课。但是大家的学习热情实在太高了，提出来的问题层出不穷，我们的老师们Hold不住了，于是老师决定让我们优秀的集训队员们来给大家指导上机。我们集训队的队员们精力非常充沛，一天到晚都是空闲时间，只要老师召唤并且要去指导的上机课的时间不冲突，那他们就一定会去指导小学弟和小学妹们(主要是小学妹们←.←)。每节上机课必须有且只有一个队员指导，但是一个队员可以连续指导多节上机课，只要时间不冲突。所谓时间不冲突，就是指要去指导的上机课的时间不重叠(比如1-3和2-4就冲突，而1-5和5-10就不冲突)。可是现在，轮到安排队员去上课的老师Hold不住了，因为他不知道这一天最少要安排多少队员来给大家上课，老师需要一个真正的ACMer来帮助他，你可以吗？

输入

输入包含多组数据。

每一组数据第一行有一个整数N(0 <= N < 1000)，表示这一天上机课的数目。接下来N行，每行有两个整数S和T, (0 <= S < T <= 24), 表示该上机课的开始时刻和结束时刻。

输出

输出一个整数代表这一天最少需要多少队员

样例输入

样例输出

提示

Sample里面只需要两个队员，一个上1门课(1-5)，另外一个上5门课(2-3,3-4,6-7,8-9,10-12).

类似贪心，只要把每节有人去的课标记一下，输出空的节数就行

#include <cstdio>

#include <cstring>

#include <algorithm>

struct demo

{

    int begint;

    int endt;

}t[];

bool cmp(demo x,demo y)

{

    return x.begint<y.begint;

}

int main()

{

    int n,i,j,s[],ans;

    while(scanf("%d",&n)!=EOF)

    {

        ans=;

        for(i=;i<=n;i++)

        {

            scanf("%d%d",&t[i].begint,&t[i].endt);

        }

        memset(s,,sizeof(s));

        std::sort(t+,t+n+,cmp);

        for(i=;i<=n;i++)

        {

            if(!s[i])

            {

                for(j=;j<=n;j++)

                {

                    if(i!=j&&!s[j])

                    {

                        if(t[j].begint>=t[i].endt)

                        {

                            t[i].endt=t[j].endt;

                            s[j]=;

                        }

                    }

                }

            }

        }

        for(i=;i<=n;i++)

        {

            if(!s[i])

                ans++;

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

hnust hold不住的老师

问题 H: Hold不住的老师

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章