題目鏈接:http://ace.delos.com/usacoprob2?a=RfmQrEONAFb&S=milk2用一個(gè)farmer_count變量來(lái)記錄當(dāng)前的farmer的數(shù)量。當(dāng)farmer從0到1時(shí)，說(shuō)明有人開(kāi)始進(jìn)來(lái)擠扔了，
計(jì)算一下之前的無(wú)人狀態(tài)的時(shí)間。當(dāng)farmer從1到0時(shí)，說(shuō)明最后一個(gè)農(nóng)夫離開(kāi)了，計(jì)算一下之前的有人擠奶狀態(tài)。
在輸入的時(shí)候，每個(gè)農(nóng)夫的進(jìn)入和離開(kāi)時(shí)間各加一個(gè)結(jié)點(diǎn).
代碼如下：
#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; //時(shí)間
int kind; //kind==0為到達(dá)時(shí)間，kind==1為離開(kāi)時(shí)間
};
node nodes[10001];
bool operator<(const node &n1, const node&n2)
{
if(n1.value!=n2.value)
return n1.value<n2.value;
else
/*
如果某一時(shí)刻有人來(lái)，有人走，這個(gè)時(shí)刻應(yīng)該是算成milking的。
所以把到達(dá)的排在前面，這樣在這個(gè)時(shí)刻就不會(huì)判斷為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;
//對(duì)時(shí)間進(jìn)行排序，因?yàn)閟ort的區(qū)間是左閉右開(kāi)的，所以要取nodes的最后一位的下一位
//TIC資格賽的時(shí)候因?yàn)檫@個(gè)問(wèn)題WA了幾次。。。
sort(&nodes[0],&nodes[2*num]);
int max_milked,max_unmilked;
//最長(zhǎng)取奶時(shí)間，最長(zhǎng)未取奶時(shí)間
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到有，說(shuō)明從無(wú)人狀態(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，說(shuō)明從有人狀態(tài)到無(wú)人狀態(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;
}