题目描述

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

发表评论

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

你是机器人吗? =。= *