先对时间段排序.
设ans1 为最长至少有一人在挤奶的时间段（nBegin, nEnd ）， ans2为最长的无人挤奶的时间段。
遍历排序后的各个时间段（t[i]）：
如果 t[i].m_nBegin <= nEnd && t[i].m_nEnd >= nEnd) 更新 nEnd = t[i].m_nEnd；
否则 更新ans1, ans2, nBegin, nEnd, 看代码。
/**//*
ID: lorelei3
PROG: milk2
LANG: C++
*/
#include <fstream>
#include <algorithm>
using namespace std;
const int N = 5005;
int n;
typedef struct TimeNode
{
int m_nBegin, m_nEnd;
bool operator < (const TimeNode& node)const{
return m_nBegin<node.m_nBegin || m_nBegin==node.m_nBegin && m_nEnd<node.m_nEnd;
}
}TimeNode, *pTimeNode;
TimeNode t[N];
int inline max(int a, int b){
return a>b?a:b;
}
int main(){
int i;
ifstream in("milk2.in");
ofstream out("milk2.out");
in>>n;
for(i=0;i<n;++i){
in>>t[i].m_nBegin>>t[i].m_nEnd;
}
sort(t, t+n);
bool f = false;
int nBegin=t[0].m_nBegin, nEnd=t[0].m_nEnd;
int ans1=nEnd-nBegin, ans2=0;
for(i=1;i<n;++i){
if(t[i].m_nBegin<=nEnd && t[i].m_nEnd>=nEnd){
nEnd = t[i].m_nEnd;
}else if(t[i].m_nBegin>nEnd){
ans1 = max(nEnd-nBegin, ans1);
ans2 = max(t[i].m_nBegin-nEnd, ans2);
nBegin = t[i].m_nBegin;
nEnd = t[i].m_nEnd;
}
}
out<<ans1<<" "<<ans2<<endl;
return 0;
}posted on 2010-11-07 00:29
小阮 阅读(418)
评论(0) 编辑 收藏 引用 所属分类:
USACO