B.上课上课上课 | 2018 校内选拔赛 预选赛 Day1

Description

ACSync 是个上课狂,大学期间曾立志要上完大学里所有的课,假设所有课都是年年开并且上课时间不变,聪明的你快来帮帮他算一下他的鸿鹄之志能否终成正果?

Input

第一行为 2 个数 N, M,分别表示课程的总数和 ACSync 可以上课的总年数;
接下来的 N 行,第 i 行为两个整数 Ai, Bi (Ai <= Bi),表示第 i 门课程的上课时间 [Ai, Bi]。

如果两门课的上课时间 [Ai, Bi] 和 [Aj, Bj] 有重合,则这两门课不能在同一年上。

对于全部测试用例,1 <= N <= 1 000; 1 <= M <= 1 000; 1 <= Ai <= Bi <= 1 000 000 000。

Output

ACSync 能否在 M 年内学完所有课程?若是,输出「Yes」,否则输出「No」。

Sample Input

3 2
1 2
2 3
3 4

Sample Output

Yes

Hint

测试样例(具体不唯一):

1 2 和 3 4 在第一年;
2 3 在第二年;
故可以。

使用结构体进行数据存储,构造 CMP 函数使用 Sort 对数组按结束时间进行排序。

题解

#include "cstring"
#include "cmath"
#include "algorithm"
#include "cstdio"
using namespace std;
struct node
{
    int start, end;//课程起止时间
    bool used;
};
inline bool cmp(node A, node B)
{
    if (A.start > B.start)//开始时间晚的课程放后边
        return 0;
    if (A.start == B.start && A.end > B.end)//开始时间相同,则结束时间晚的课程放后边
        return 0;
    return 1;
}
int main()
{
    int n,m;
    /**
     * n 课程数
     * m 年份数
     */
    scanf("%d%d", &n, &m);
    node course[n];
    memset(course, 0, sizeof(course));
    for (int i = 0; i < n; i++)
        scanf("%d%d", &course[i].start, &course[i].end);

    int sum = 0;
    for (int i = 0; i < m; i++)//i 当前年份
    {
        sort(course, course + n, cmp);
        int end = 0;//上节课的时间
        for (int j = 0; j < n; j++)
        {
            if (!course[j].used)
            {
                if (course[j].start > end)
                {
                    end = course[j].end;
                    course[j].used = 1;
                    sum++;
                }
            }
        }
    }
    //debug
    // printf("sum == %d\n", sum);
    printf(sum == n ? "Yes" : "No");
    return 0;
}

CC BY-SA 4.0 B.上课上课上课 | 2018 校内选拔赛 预选赛 Day1 by 小小泥娃的部落格 is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论