Description

幽會計劃

二哥如今在TNCM機(jī)場做空管。二哥不幸被分配到了進(jìn)近席，進(jìn)近席位要負(fù)責(zé)處理所有準(zhǔn)備降落在機(jī)場的飛機(jī)，讓他們平穩(wěn)地落在跑道上。飛機(jī)降落一般遵循五邊進(jìn)近航圖，不過在這道題目中你不需要關(guān)心什么是五邊進(jìn)近，只要看下面這張圖。

一架飛機(jī)總是從下滑道入口（A點）開始接受二哥管制，直到降落成功（B點）。飛機(jī)不會是同一型號的，速度也不一樣，所以從A點到B點所需的時間不同。二哥得小心一點，不能把事情搞砸了：（1）下滑道內(nèi)不允許飛機(jī)互相超越；（2）一架飛機(jī)降落之后，至少要等待一段時間才允許下一架飛機(jī)降落（即到達(dá)B的時間間隔要大于等于一個值）。

二哥是個聰明的人，他寫了一個程序來幫他控制所有飛機(jī)，然后他就可以喝茶去了。二哥的策略是：通過拒絕某些飛機(jī)進(jìn)入下滑道，來保證下滑道上的飛機(jī)永遠(yuǎn)不會距離太近。也就是說，只要飛機(jī)被允許進(jìn)入下滑道，就可以安全降落。

每當(dāng)一架飛機(jī)來到下滑道的入口時，二哥的程序就會判斷：如果允許這架飛機(jī)進(jìn)入下滑道，它能否安全降落。如果能安全降落，二哥就允許他進(jìn)入下滑道，否則二哥會立即要求這架飛機(jī)在A點復(fù)飛。

原則上，兩架飛機(jī)不應(yīng)該同時出現(xiàn)在A點，但這種情況顯然可能出現(xiàn)。如果真的出現(xiàn)了這種情況，則說明空管局這次徹底把事情搞砸，二哥的策略顯然可能是誘因。

簡單來說，在未來的一段時間內(nèi)，共有N架飛機(jī)要降落，他們會在Ti時刻首次出現(xiàn)在下滑道入口，他們從A點到B點需要的時間為Ui。如果他們被二哥命令在A點復(fù)飛，他們會在Gi分鐘后再次出現(xiàn)在下滑道入口。飛機(jī)的安全降落間隔是S。

現(xiàn)在，二哥的女朋友找到你，請你計算一下每架飛機(jī)會在第幾分鐘完成降落。這樣她可以估算出二哥什么時候下班，以便瞞著二哥去和情人去幽會。

Input Format

第一行有三個正整數(shù)N、MAX、S，表示有多少飛機(jī)，最長模擬的時間，以及安全降落時間間隔。

之后有N行，每行有三個非負(fù)整數(shù)，依次為Ti、Ui、Gi，分別表示第i架飛機(jī)的首次到達(dá)時間、從A點到B點耗時、復(fù)飛耗時。

N≤1000

MAX≤1000000 S≤1000 Ti≤1000000 ，Ui≤1000 ，Gi≤1000

Output Format

假設(shè)在MAX時刻之前([0..MAX-1])，有飛機(jī)同時出現(xiàn)在了下滑道口，則輸出“CHANGE BOYFRIEND”，因為飛機(jī)撞了，三哥估計要下崗了，她可以換一個男朋友了。

假設(shè)在MAX時刻之前沒有飛機(jī)相撞，但模擬結(jié)束后仍然有飛機(jī)沒有降落，則輸出一行“GO DATING”，以表示三哥的女朋友可以放心大膽地幽會去了。

否則輸出N行，每行一個整數(shù)，表示第i架飛機(jī)最終降落的時刻。

Sample Input

4 20 2
0 2 5
1 2 1
5 2 1
6 10 10

Sample Output

2
4
7
16

Sample Input

3 10 2
0 2 5
1 2 3
4 1 1

Sample Output

CHANGE BOYFRIEND

樣例解釋

分析：0時刻，第一架飛機(jī)到達(dá)A，二哥允許他進(jìn)入下滑道，在第2時刻降落。1時刻，第二架飛機(jī)到達(dá)A，二哥要求他復(fù)飛，因為降落間距小于安全標(biāo)準(zhǔn)。2時刻，第二架飛機(jī)復(fù)飛后再次回到A，二哥允許他進(jìn)入下滑道，在第4時刻降落。5時刻，第三架飛機(jī)到達(dá)A，二哥允許他進(jìn)入下滑道，在第7時刻降落6時刻，第四架飛機(jī)到達(dá)A，二哥允許他降落，在第16時刻降落。分析：在4時刻，第二架飛機(jī)和第三架飛機(jī)會相撞。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>using namespace std;class Fly{
public:int id,in,out,repStay;Fly(int fid,int a, int b, int c){id = fid;in = a;out = b;repStay = c;}Fly(){};
};int main()
{int n,Max,s,N;cin>>n>>Max>>s;N = n;map<int, Fly> fly;int fid = 0;while(n-->0){int in,out,repStay;cin>>in>>out>>repStay;fly[in] = Fly(fid,in,out,repStay);fid++;}int res[N];map<int, Fly>::iterator iter = fly.begin();int lastLoad = iter->second.in + iter->second.out;iter++;res[0] = lastLoad;while(iter != fly.end()){if(iter->second.in>=Max){cout<<"GO DATING";return 0;}int achi = iter->second.in + iter->second.out;if(achi-lastLoad>=s){res[iter->second.id] = achi;lastLoad = achi;}else{int n_in = iter->second.in + iter->second.repStay;if(fly.count(n_in)>0){cout<<"CHANGE BOYFRIEND";return 0;}else{fly[n_in] = Fly(iter->second.id, n_in, iter->second.out, iter->second.repStay);}}iter++;}for(int i=0;i<N;i++)cout<<res[i]<<" "<<endl;return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/bernieloveslife/p/7890136.html

總結(jié)

以上是生活随笔為你收集整理的1027. 戴绿帽子的空管的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。