随笔-141  评论-9  文章-3  trackbacks-0
先对时间段排序.

设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 小阮 阅读(412) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理