題目網址:A - Bot Trust

題目概述

有兩個機器人 Orange 跟 Blue,他們各自被困在一個長長的走廊中。走廊的牆上有 100 個按鈕,按鈕上分別標著 1 ~ 100,按鈕 k 總是距離走廊的起點 k 公尺。每一秒,機器人可以往某方向前進 1 公尺,或是留在原地。留在原地時,可以選擇按下該位置之按鈕或是不做任何動作。

現在給定這兩機器人需要按下按鈕的時間點清單,兩個機器人最初都位在按鈕 1 的位置。求出最少需要多少時間可以完成此清單之要求。

Technique Detail

small case

  • 測試資料的數量 T, 1 ≤ T ≤ 20
  • 需要被按下的按鈕數量 N, 1 ≤ N ≤ 10

large case

  • 測試資料的數量 T, 1 ≤ T ≤ 20
  • 需要被按下的按鈕數量 N, 1 ≤ N ≤ 10

輸入格式

每一筆測試資料由一個整數 T 開始,表示接下來有 T 組測試資料。

每一組測試資料由一個整數 N 開始,即為需要被按下的按鈕數量。接下來會有 N 組含兩個整數的按鈕資料 Ri, Pi。Ri 表機器人的顏色,以 O 表示 Orange;B 表示 Blue。而 Pi 為按鈕編號。

輸出格式

對於每一筆測試資料,輸出只有一行,輸出測試資料編號與一個整數 Case #X: Y。X 為測試資料編號,由 1 開始;Y 為最少所需要的時間。


解題思路

在給定清單時,依照 O 與 B 存在不同的 queue 上,儲存時也記錄此對資料的時間點。接著開始模擬,看 O 與 B 誰的時間點較早,就先處理。

假設 O 按下按鈕的時間較早,我們就先處理 O,也就是直接把 O 移動到他所要按的按鈕位置,並按下按鈕(時間 + 1),再將花去的時間加上。此時,B 也須做處理,B 要盡可能的移動到 B 下一個所要按的按鈕的位置,但不可按下按鈕,反之亦然。

另一種情況是,O 或 B 已沒有需要按的按鈕了,此時就處理另一個還有按鈕清單的機器人即可。直到兩方都沒有按鈕需要按時,程式終止,輸出答案即可。

時間複雜度為 O(N),對每次按下按鈕處理一次即可。

Time Complexity: O( N )

Source Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
int test = 0;
freopen( "A.out", "w", stdout );
scanf( "%d", &test );
for ( int t = 0; t < test; ++t ) {
int n;
queue< pair< int, int > > B, O;
scanf( "%d", &n );
int x;
char c;
for ( int i = 0; i < n; ++i ) {
scanf( " %c %d", &c, &x );
if ( c == 'B' )
B.push( pair< int, int >( i, x ) );
else
O.push( pair< int, int >( i, x ) );
}
int cnt = 0, posB = 1, posO = 1;
while ( !B.empty() || !O.empty() ) {
if ( ( !B.empty() && !O.empty() && O.front().first < B.front().first ) || B.empty() ) {
int step = abs( posO - O.front().second ) + 1;
cnt += step;
posO = O.front().second;
O.pop();
if ( !B.empty() ) {
if ( B.front().second < posB )
posB = max( posB - step, B.front().second );
else
posB = min( posB + step, B.front().second );
}
}
else if ( ( !B.empty() && !O.empty() && B.front().first < O.front().first ) || O.empty() ) {
int step = abs( posB - B.front().second ) + 1;
cnt += step;
posB = B.front().second;
B.pop();
if ( !O.empty() ) {
if ( O.front().second < posO )
posO = max( posO - step, O.front().second );
else
posO = min( posO + step, O.front().second );
}
}
}
printf( "Case #%d: %d\n", t + 1, cnt );
}
return 0;
}

Source code on gist.