洛谷-P1204 [USACO1.2]挤牛奶Milking Cows

洛谷-P1204 [USACO1.2]挤牛奶Milking Cows

原题链接：https://www.luogu.com.cn/problem/P1204

• 题目描述
• 输入格式
• 输出格式
• 输入输出样例
• 说明/提示
• C++代码

---

题目描述

三个农民每天清晨 (5) 点起床，然后去牛棚给三头牛挤奶。

第一个农民在 (300) 秒 (从 (5) 点开始计时) 给他的牛挤奶，一直到 (1000) 秒。第二个农民在 (700) 秒开始，在 (1200) 秒结束。第三个农民在 (1500) 秒开始，(2100) 秒结束。

期间最长的至少有一个农民在挤奶的连续时间为 (900) 秒 (从 (300) 秒到 (1200) 秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为 (300) 秒 (从 (1200) 秒到 (1500) 秒)。

---

你的任务是编一个程序，读入一个有 (n) 个农民挤 (n) 头牛的工作时间列表，计算以下两点(均以秒为单位):

最长至少有一人在挤奶的时间段。

最长的无人挤奶的时间段。（从有人挤奶开始算起）

输入格式

第一行一个正整数 (n)

接下来 (n) 行，每行两个非负整数 (l,r)，表示一个农民的开始时刻与结束时刻。

输出格式

一行，两个整数，即题目所要求的两个答案。

输入输出样例

输入 #1

3
300 1000
700 1200
1500 2100

输出 #1

900 300

说明/提示

【数据范围】
对于 (100\%) 的数据，(1le n le 5000)，(0 le l le r le 10^6)。

题目翻译来自NOCOW。

USACO Training Section 1.2

C++代码

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

struct node {
    int l, r;
}t[5005];

bool cmp(node x, node y) {
    return x.l < y.l;
}

int main() {
    int n, start, end, ans1=0, ans2=0;
    cin >> n;
    for (int i=0; i<n; ++i)
        cin >> t[i].l >> t[i].r;
    sort(t, t+n, cmp);
    start = t[0].l;
    end = t[0].r;
    for (int i=1; i<n; ++i)
        if (t[i].l <= end)
            end = max(end, t[i].r);
        else {
            ans1 = max(ans1, end - start);
            ans2 = max(ans2, t[i].l - end);
            start = t[i].l;
            end = t[i].r;
        }
    ans1 = max(ans1, end-start);
    cout << ans1 << ' ' << ans2 << endl;
    return 0;
}