【题解】[USACO1.2] 挤牛奶 Milking Cows

题目描述

三个农民每天清晨 5 点起床，然后去牛棚给 3 头牛挤奶。第一个农民在 300 秒 (从 5 点开始计时) 给他的牛挤奶，一直到 1000 秒。第二个农民在 700 秒开始，在 1200 秒结束。第三个农民在 1500 秒开始 2100 秒结束。期间最长的至少有一个农民在挤奶的连续时间为 900 秒 (从 300 秒到 1200 秒)，而最长的无人挤奶的连续时间 (从挤奶开始一直到挤奶结束) 为 300 秒 (从 1200 秒到 1500 秒)。
你的任务是编一个程序，读入一个有 N 个农民 (1 <= N <= 5000) 挤 N 头牛的工作时间列表，计算以下两点 (均以秒为单位):
最长至少有一人在挤奶的时间段。
最长的无人挤奶的时间段。（从有人挤奶开始算起）
输入输出格式
输入格式：

Line 1:

一个整数 N。

Lines 2..N+1:

每行两个小于 1000000 的非负整数，表示一个农民的开始时刻与结束时刻。

输出格式：

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

输入样例：

3

300 1000

700 1200

1500 2100

输出样例：

900 300

思路：离散化，把每个开始和结束看做一个事件来处理。根据时间顺序排序以后计算答案。具体看代码：

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
int n,a1,a2,l,c;
vector<pair<int,bool> >events;pair<int,bool> ne;
bool cmp(pair<int,bool> a,pair<int,bool> b){if(a.first==b.first)return a.second?1:0;return a.first<b.first;}
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>ne.first;ne.second=1;events.push_back(ne);
        cin>>ne.first;ne.second=0;events.push_back(ne);
    }
    sort(events.begin(),events.end(),cmp);
    l=events[0].first;
    for(vector<pair<int,bool> >::iterator it=events.begin();it!=events.end();it++)
        if(it->second==1){if(++c==1){a2=max(a2,it->first-l),l=it->first;}}
        else{if(!--c){a1=max(a1,it->first-l),l=it->first;}}
    cout<<a1<<' '<<a2;
    return 0;
}