題目鏈接:http://ace.delos.com/usacoprob2?a=RfmQrEONAFb&S=milk2用一個farmer_count變量來記錄當(dāng)前的farmer的數(shù)量。當(dāng)farmer從0到1時，說明有人開始進來擠扔了，
計算一下之前的無人狀態(tài)的時間。當(dāng)farmer從1到0時，說明最后一個農(nóng)夫離開了，計算一下之前的有人擠奶狀態(tài)。
在輸入的時候，每個農(nóng)夫的進入和離開時間各加一個結(jié)點.
代碼如下：
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("milk2.in");
ofstream fout("milk2.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
struct node{
int value; //時間
int kind; //kind==0為到達時間，kind==1為離開時間
};
node nodes[10001];
bool operator<(const node &n1, const node&n2)
{
if(n1.value!=n2.value)
return n1.value<n2.value;
else
/*
如果某一時刻有人來，有人走，這個時刻應(yīng)該是算成milking的。
所以把到達的排在前面，這樣在這個時刻就不會判斷為unmilking狀態(tài)了。
*/
return n1.kind<n2.kind;
}
void solve()
{
int num;
in>>num;
int begin,end;
for(int i=0;i<num;++i){
in>>begin>>end;
nodes[2*i].value = begin;
nodes[2*i].kind = 0;
nodes[2*i+1].value = end;
nodes[2*i+1].kind = 1;
}
int last_milk_time = nodes[0].value;
int last_unmilk_time = INT_MIN;
//對時間進行排序，因為sort的區(qū)間是左閉右開的，所以要取nodes的最后一位的下一位
//TIC資格賽的時候因為這個問題WA了幾次。。。
sort(&nodes[0],&nodes[2*num]);
int max_milked,max_unmilked;
//最長取奶時間，最長未取奶時間
max_milked = max_unmilked = 0;
//當(dāng)前的農(nóng)夫數(shù)
int farmer_count = 0;
for(int i=0;i<2*num;++i){
if(nodes[i].kind==0){
if(farmer_count==0){
//農(nóng)夫數(shù)從0到有，說明從無人狀態(tài)到有人狀態(tài)
max_unmilked = max(max_unmilked,nodes[i].value-last_unmilk_time);
last_milk_time = nodes[i].value;
}
farmer_count++;
}else{
if(farmer_count==1){
//農(nóng)夫數(shù)從1到0，說明從有人狀態(tài)到無人狀態(tài)
max_milked = max(max_milked,nodes[i].value-last_milk_time);
last_unmilk_time = nodes[i].value;
}
farmer_count--;
}
}
//max_unmilked最大為0.
out<<max_milked<<" "<<max(max_unmilked,0)<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}