HDU 5240 Exam

题目链接:点击这里

image.png

image.png

题意:给出若干门课需要的复习时间$r$、考试开始时间$e$和考试持续时间$l$,求这个人能否参加和通过所有考试。

思路:按照考试开始时间排序,看是否有重合的区间(即判断 $e_i-e_{i-1}$ 是否小于 $r_i+l_{i-1}$ )

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

struct node
{
    int r, e, l;
}a[N];

bool cmp(node a, node b)
{
    return a.e < b.e;
}

int main()
{
    int T;
    scanf("%d", &T);
    for(int k = 1; k <= T; k++)
    {
        int n;
        scanf("%d", &n);
        
        a[0].r = 0, a[0].e = 0, a[0].l = 0;
        for(int i = 1; i <= n; i++)    scanf("%d%d%d", &a[i].r, &a[i].e, &a[i].l);
        
        sort(a + 1, a + n + 1, cmp);
        
        bool flag = true;
        for(int i = 1; i <= n; i++)
        {
            if(a[i].e - a[i - 1].e < a[i].r + a[i - 1].l)
            {
                flag = false;
                break;
            }
        }
        
        printf("Case #%d: ", k);
        if(flag)    puts("YES");
        else    puts("NO");
    }
    
    return 0;
}

评论

暂无评论