HDU 5240. Exam

Author: 2015-08-18

ACM

, ,

1. 题目

http://acm.hdu.edu.cn/showproblem.php?pid=5240

Exam

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 694    Accepted Submission(s): 348

Problem Description
As this term is going to end, DRD needs to prepare for his final exams.DRD has n exams. They are all hard, but their difficulties are different. DRD will spend at least ri hours on the i-th course before its exam starts, or he will fail it. The i-th course’s exam will take place ei hours later from now, and it will last for li hours. When DRD takes an exam, he must devote himself to this exam and cannot (p)review any courses. Note that DRD can review for discontinuous time.So he wonder whether he can pass all of his courses.
No two exams will collide.

Input
First line: an positive integer T≤20 indicating the number of test cases.
There are T cases following. In each case, the first line contains an positive integer n≤105, and n lines follow. In each of these lines, there are 3 integers ri,ei,li, where 0≤ri,ei,li≤109.
Output
For each test case: output ”Case #x: ans” (without quotes), where x is the number of test cases, and ans is ”YES” (without quotes) if DRD can pass all the courses, and otherwise ”NO” (without quotes).
Sample Input
2
3
3 2 2
5 100 2
7 1000 2
3
3 10 2
5 100 2
7 1000 2
Sample Output
Case #1: NO
Case #2: YES
Source
The 2015 ACM-ICPC China Shanghai Metropolitan Programming Contest

2. 思路

给出一组考试，对于第i门考试，事前需要ri个小时复（预）习才能通过，考试开始于第ei个小时，持续li个小时。求是否能通过所有的考试，即参加所有的考试，且保证各门考试前都有足够时间复习。
贪心算法。根据考试开始时刻ei，对考试列表进行升序排序，然后遍历列表。对于第1门考试，如果所需预习时间大于考试开始时间，则无法通过，直接返回；反之可以通过，将第一门考试所需的复习时间和考试的持续时间，累加进第2门考试的复习时间里，继续判断是否有足够的时间复习第2门考试，以此类推。成功遍历完所有考试，则可以全部通过。

3. 代码

#include <stdio.h>
#include <stdlib.h>

#define MAX_EXAM_NUM 100000
#define REVIEW_NEEDED 0
#define EXAM_START 1
#define EXAM_DURATION 2

typedef int Schedule[MAX_EXAM_NUM][3];

bool solveE4c_Exam();
int inputSchedule(Schedule schedule);
int cmp(const void *a, const void *b);

int main() {
    int testcaseNum;
    scanf("%d", &testcaseNum);

    bool canPass;
    for (int i = 1; i <= testcaseNum; ++i) {
        canPass = solveE4c_Exam();
        printf("Case #%d: ", i);
        if (canPass)
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}

Schedule schedule;
bool solveE4c_Exam() {
    int examNum = inputSchedule(schedule);
    qsort(schedule, examNum, sizeof(int)*3, cmp);

    int i;
    for (i = 0; i < examNum; ++i) {
        if (schedule[i][REVIEW_NEEDED] > schedule[i][EXAM_START]) {
            return false;
        } else {
            schedule[i + 1][REVIEW_NEEDED] += schedule[i][REVIEW_NEEDED] + schedule[i][EXAM_DURATION];
        }
    }

    return schedule[i][REVIEW_NEEDED] > schedule[i][EXAM_START];
}

int inputSchedule(Schedule schedule) {
    int examNum;
    scanf("%d", &examNum);

    for (int i = 0; i < examNum; ++i) {
        scanf("%d %d %d", &schedule[i][REVIEW_NEEDED], &schedule[i][EXAM_START], &schedule[i][EXAM_DURATION]);
    }

    return examNum;
}

int cmp(const void *a, const void *b) {
    return *((int *)a + EXAM_START) - *((int *)b + EXAM_START);
}