USACO Milking Cows(模擬)

USACO Milking Cows(模擬)

題意：
題意很簡單，最開始的時候想要用優先隊列存儲時間，用map存儲對應時間起點與終點。按時間軸順序排列的思路是沒錯的，但是忽略了很重要的一點，一個時間起點可能會有多個對應的時間終點。改用結構體存儲，定義cmp，得到時間軸。有兩個變量表示總的時間起點和終點，注意起點與終點變換的條件，不斷向後遍歷就可以了。
代碼實現：

/*
ID: eashion
LANG: C++
TASK: milk2
*/
#include 
#include 
#include 
#include 
#include 
#define MAX 5050

using namespace std;

struct node{
    int Tstart,Tend;
};

int N;
int T1;//起點
int T2;//終點
int res1,res2;
node Nlis[MAX];
bool cmp(const node a,const node b){
    if( a.Tstart != b.Tstart ){
        return a.Tstart < b.Tstart;
    }
    return a.Tend < b.Tend;
}
int main()
{
    freopen(milk2.in,r,stdin);
    freopen(milk2.out,w,stdout);
    scanf(%d,&N);
    for( int i = 0; i < N; i++ ){
        scanf(%d%d,&Nlis[i].Tstart,&Nlis[i].Tend);
    }
    sort(Nlis,Nlis+N,cmp);
    T1 = Nlis[0].Tstart;
    T2 = Nlis[0].Tend;
    res1 = res2 = 0;
    for( int i = 0; i < N; i++ ){
        if( T2 >= Nlis[i].Tstart ){
            T2 = max( T2,Nlis[i].Tend );
            res1 = max( T2-T1,res1 );
        }
        else{
            T1 = Nlis[i].Tstart;
            res2 = max( res2,T1-T2 );
            T2 = Nlis[i].Tend;
        }
    }
    printf(%d %d
,res1,res2);
    return 0;
}