題目 1946:
藍(lán)橋杯算法提高VIP-A Careful Approach
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 64 解決: 17
題目描述
如果你認(rèn)為參加一個編程比賽讓你感到有壓力，那么請你想象你是一個空中交通管制員。因?yàn)槿嗣P(guān)天，所以一個空中交通管制員必須在時(shí)刻變化的環(huán)境中專注于任務(wù)，解決不可預(yù)知的事件。
讓我們將目光轉(zhuǎn)向飛機(jī)的著陸流程。飛機(jī)進(jìn)入目的地飛航情報(bào)區(qū)之后，就會報(bào)告自己的位置、方向和速度，然后管制員就需要制定計(jì)劃讓所有飛機(jī)按指令安全著陸。一般來說，連續(xù)的兩次著陸之間間隔時(shí)間越長，就越安全。因?yàn)檫@些額外的時(shí)間能夠讓工程師有機(jī)會對天氣變化以及其他突發(fā)事件作出反應(yīng)。
幸運(yùn)的是，有一部分計(jì)劃的制定可以自動化——這就是你來這里的原因。你會得到有關(guān)飛機(jī)著陸的腳本。每一個飛機(jī)都有一個安全著陸時(shí)間窗。你算出的指令必須要符合每個飛機(jī)的時(shí)間窗。另外，飛機(jī)的著陸時(shí)間點(diǎn)要盡量均勻，使得連續(xù)兩次著陸的最小間隔盡量大。例如，如果三架飛機(jī)分別著陸于10:00am、10:05am、10:15am，那么最小間隔是五分鐘，在頭兩架飛機(jī)之間。所有間隔不一定一樣，但是最小的間隔要盡量大。
輸入格式
多組數(shù)據(jù)。每個數(shù)據(jù)第一行為一個整數(shù)n，為飛機(jī)架數(shù)。接下來n行，每行兩個整數(shù)a[i]，b[i]表示這架飛機(jī)只能在閉區(qū)間[a[i],b[i]]間降落。a[i]和b[i]的單位是分鐘。輸入的最后一行是一個零。
輸出格式
對于每組數(shù)據(jù)，先輸出第幾組，然后輸出最小間隔，單位為分和秒，舍入到最近的整數(shù)。格式參見樣例。
樣例輸入
3
0 10
5 15
10 15
2
0 10
10 20
0
樣例輸出
Case 1: 7:30
Case 2: 20:00
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情
標(biāo)簽