CF479C

发布时间 2023-11-15 19:33:19作者: To_Carpe_Diem

题目描述(翻译)

Valera 是大学的本科生。他的期末考试即将来临,他必须要通过恰好 \(n\) 门考试。Valera 是一个聪明的人,他可以在第一次尝试时通过任何一门考试。此外,他可以在一天内考多门考试,并且可以以任意顺序进行考试。

根据考试时间表,他可以在第 \(i\) 门课程上考试的日期是 \(a _ {i}\) 。然而,Valera 与每一门课的教师都进行了安排,允许他在 \(b _ {i}\) 之前的时间来进行考试(其中 \(b _ {i} < a _ {i}\) )。因此,Valera 可以选择在第 \(i\) 门课程上的考试要么在 \(a _ {i}\) 的日期上进行,要么在 \(b _ {i}\) 的日期上进行。所有的教师都会在实际考试的日期将考试记录在学生的记录册中,并将考试的日期记为 \(a _ {i}\)

Valera 认为,如果记录册中的记录不按照非递减的日期排序,那将会很奇怪。因此,他请你帮助他。找到当 Valera 按照非递减的日期顺序进行考试时,他可以进行最后一门考试的最小日期

题目分析

Valera 需要按照非递减日期的顺序进行考试,所以我们需要找到最早可以进行最后一门考试的日期。

我们可以对考试时间表中的考试按照开始时间进行排序。

然后,我们用一个变量 lastExam 来记录最后一门考试的时间。我们从第一门考试开始,将其结束时间存储在 lastExam 中。

接下来,我们遍历剩余的考试,如果当前考试的结束时间不小于 lastExam,则将 lastExam 更新为当前考试的结束时间;否则将 lastExam 更新为当前考试的开始时间(即在老师允许的最早时间进行考试)。

最后,输出最后一门考试的时间 lastExam

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;

int main() {
    
    cin >> n;

    vector < pair < int, int > > exam(n);

    for (int i = 0; i < n; i++) {
        cin >> exam[i].first >> exam[i].second;
    }

    sort(exam.begin(), exam.end());

    int last = exam[0].second;
    for (int i = 1; i < n; i++) {
        if (exam[i].second >= last) {
            last = exam[i].second;
        } else {
            last = exam[i].first;
        }
    }

    cout << last << endl;

    return 0;
}

AC 记录