题目描述

三个农民每天清晨 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;
}

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注