程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> USACO Milking Cows(模擬)

USACO Milking Cows(模擬)

編輯:關於C++


題意:
題意很簡單,最開始的時候想要用優先隊列存儲時間,用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;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved