USACO 2014 DEC SILVER

一、題目概覽

中文題目名稱	回程	馬拉松	奶牛慢跑
英文題目名稱	piggyback	marathon	cowjog
可執行文件名	piggyback	marathon	cowjog
輸入文件名	piggyback.in	marathon.in	cowjog.in
輸出文件名	piggyback.out	marathon.out	cowjog.out
每個測試點時限	1秒	1秒	1秒
測試點數目	10	10	10
每個測試點分值	10	10	10
比較方式	全文比較	全文比較	全文比較

二、運行內存限制

運行內存上限

128 M

128 M

128 M

?

1.回程{piggyback}

【問題描述】

Bessie 和 Elsie在不同的區域放牧，他們希望花費最小的能量返回谷倉。從一個區域走到一個相連區域，Bessie要花費B單位的能量，Elsie要花費E單位的能量。

如果某次他們兩走到同一個區域，Bessie 可以背著 Elsie走路，花費P單位的能量走到另外一個相連的區域，滿足P<B+E。

相遇后，他們可以一直背著走，也可以獨立分開。

【文件輸入】

?? 第一行，五個不超過40,000的正整數B, E, P, N和M。其中N表示區域的個數（區域分別用1..N編號，N>=3）,M表示各個區域之間連接的雙向邊的邊數。一開始Bessie在區域1， Elsie在區域2，谷倉在區域N。

?? 接下來M行，每行二個整數表示一條雙向邊連接兩個區域，輸入保證從區域1和區域2都能走到區域N。

【文件輸出】

?? 一行，一個整數，最小花費的單位能量。

【輸入樣例】

4 4 5 8 8

1 4

2 3

3 4

4 7

2 5

5 6

6 8

7 8

【輸出樣例】

22

【樣例說明】

Bessie從1到4，Elsie從2到3到4，然后一起從4到7到8。

2. 馬拉松{marathon}

【問題描述】

Bessie參加城市馬拉松比賽，要順序經過N (3 <= N <= 500)個檢查點，其中檢查點1是起點，檢查點N是終點。??? Bessie嘗試略過K(K < N)個檢查點，以減少總路程，檢查點1和檢查點N不能被略過。兩個檢查點的距離是|x1-x2| + |y1-y2|。

【文件輸入】

?? 一行，兩個整數N 和 K。

接下來N行，每行兩個整數X和Y，(-1000 <= x <= 1000, -1000 <= y <= 1000)，表示N個檢查點的坐標，這N個檢查點是按順序給出的，所以必須被按順序經過。注意，同一個檢查點可能會多次出現，當某次Bessie略過該檢查點時，他只能略過當前的一次，而不是同時略過該檢查點的所有出現次數。

【文件輸出】

?? 一行，一個整數，表示Bessie經過的總路程。

【輸入樣例】

5 2

0 0

8 3

1 1

10 -5

2 2

【輸出樣例】

4

【樣例說明】

略過檢查點(8, 3) and (10, -5)。

3.奶牛慢跑{ cowjog}

【問題描述】

有N (1 <= N <= 100,000)頭奶牛在一個單人的超長跑道上慢跑，每頭牛的起點位置都不同。由于是單人跑道，所有他們之間不能相互超越。當一頭速度快的奶牛追上另外一頭奶牛的時候，他必須降速成同等速度。我們把這些跑走同一個位置而且同等速度的?？闯梢粋€小組。

請計算T (1 <= T <= 1,000,000,000)時間后，奶牛們將分為多少小組。

【文件輸入】

第一行，兩個整數N和T。

接下來N行，每行兩個數，分別表示每頭牛的初始位置P和初始速度S。其中（0<=P<=1000,000,000）、（1<=S<=1000,000,000）。輸入數據按初始位置從小到大的順序給出。

【文件輸出】

一行，一個整數，表示小組數量。

【輸入樣例】

5 3

0 1

1 2

2 3

3 2

6 1

【輸出樣例】

3

轉載于:https://www.cnblogs.com/jznoi/p/4280805.html

總結

以上是生活随笔為你收集整理的USACO翻译：USACO 2014 DEC Silver三题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。