先对时间段排序.
设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