# 題目: UVa 11034 - Ferry Loading IV # 題目說明 有車子想要渡河，目前唯一渡河的方式為搭船 船只有一艘且長度有限，求所有車子到達對岸時船的趟數 INPUT: 第一行有一個整數 c ，代表有 c 筆資料 每筆測資第一行有兩個整數 l 、 m l 代表船的長度 m 代表等待過河的車子數量 接下來有 m 行，每行有一個整數和一個字串 整數代表車子的長度 字串代表它處於河的哪一邊 OUTPUT: 將所有車子運送到對岸，船需要開的趟數 # 解題方法 以兩個 queue 分別存左岸及右岸的車子的長度 接著跑迴圈直到兩個 queue...

# 題目: UVa 10901 - Ferry Loading III # 題目說明 有車子想要渡河，目前唯一渡河的方式為搭船 船只有一艘且容量有限，求所有車子到達對岸的時間 INPUT: 第一行有一個整數 c ，代表有 c 筆資料 每筆測資第一行有三個整數 n 、 t 、 m n 代表船能容納的車子數量 t 代表船開到對岸的時間 m 代表等待過河的車子數量 接下來有 m 行，每行有一個整數和一個字串，整數代表車子到岸邊的時間，字串代表它處於河的哪一邊 OUTPUT: 輸出每輛車子到達對岸的時間 每筆資料以空行隔開 # 解題方法 以兩個 queue...

# 題目: UVa 10172 - The Lonesome Cargo Distributor # 題目說明 有一輛貨車跟數個站點，貨車與站點的容量有限制 貨車每到一個站會執行以下動作 將車上的貨物卸下，如果是目標貨物直接卸下，否則放到站點的 queue 中 將站點中的貨物裝到車上 移動到下一個站點 花費時間: 每次裝貨及卸貨都會花費 1 分鐘 移動到下一個站點會花費 2 分鐘 求所有貨物放到目標站點所花費的時間 INPUT: 第一行有一個整數 SET ，代表有幾筆資料 每筆資料的第一行有三個整數 N 、 S 、 Q N 代表有幾站、 S 代表貨車可裝載貨物量、 Q 代表站點中...

# 題目: UVa 1062 – Containers # 題目說明 船運送貨物到港口，貨物需要依 A 到 Z 的順序排序 字母大的貨物在下，且字母大的貨物不能放在比它小的上方 求貨物至少要先堆成幾堆才能達成 INPUT: 每筆資料輸入一個字串，代表貨物到港口的順序 當輸入為 end 時結束程式 OUTPUT: 先輸出第幾個 case 接著輸出需要的最小 stack 數 # 解題方法 其實這題就是在求 LIS : 最長嚴格遞增子陣列 利用 greedy演算法 求出 LIS # 參考程式碼 #include <iostream>#include...

# 題目: UVa 732 - Anagrams by Stack # 題目說明 給你兩個字串及一個 stack ，找出所有能使前者變成後者的所有 input 、 output 組合 INPUT: 每筆資料輸入兩個字串，起始字串及目標字串 OUTPUT: 輸出起始字串能透過 stack 轉變為目標字串的所有組合 # 解題方法 使用 dfs，每次將字串 push 及 pop ，最後如果符合目標字串則輸出 # 參考程式碼 #include <iostream>#include <stack>using namespace std;string in,...

# 題目: UVa 514 - Rails # 題目說明 有一個火車站，出去及進來都只有一條路 有一對列按照編號順序排列的火車 它們是否能按照特定順序出車站？ INPUT: 每筆資料的第一行有一個整數 n ，代表有 n 個火車 接著有 n 個整數，代表火車出站的順序 當第一個順序為 0 時，結束這筆資料 當 n 為 0 時，結束程式 OUTPUT: 當順序為可行時，輸出 Yes ，否則輸出 No # 解題方法 用 stack a 儲存資料，按照順序找到火車 (判斷 stack a 及 stack b 的 top ) 並將這台火車前面的火車都 push 到 stack b 如果過程中...

# 題目: UVa 11995 - I Can Guess the Data Structure! # 題目說明 你能猜到資料結構嗎？ 給你一些 push 和 pop data，找出資料結構 INPUT: 每筆資料的第一行有一個整數 n ，代表接下來有 n 行 每行有兩個整數，前者代表指令， 1 為 push ， 2 為 pop ，後者代表數字 OUTPUT: stack queue priority queue 都不是 impossible 兩種以上容器符合 not sure # 解題方法 分別 push 到 3 種容器中做模擬，看有幾個符合 # 參考程式碼 #include...

# 題目: UVa 10954 - Add All # 題目說明 題目說明了你的目標: 加全 例如 1 + 2 + 3 先 1 + 2 cost 3 再 3 + 3 cost 6 總共 cost 9 INPUT: 每筆資料的第一行有一個整數 N ，代表接下來有 N 個整數 當 N 為 0 時結束程式 OUTPUT: 輸出全部相加所需最少的 cost # 解題方法 用 priority queue 儲存資料 (升冪排序) 每次取最前 (小) 兩個做相加即可 # 參考程式碼 #include <iostream>#include <queue>using...

# 題目: UVa 1203 - Argus # 題目說明 我們在 Argus 註冊了很多 Register 你的目標是找到錢 K 個 Register INPUT: 每行輸入 3 個字串 Register 或 # ，當輸入為 # 結束 Register 的編號 Register 的頻率 最後有一個整數 K ，代表要輸出幾個 Register OUTPUT: 輸出 K 個 Register 的編號，如果頻率相同，則編號小的優先輸出 # 解題方法 用 priority queue 儲存編號及頻率 (升冪排序) 每次找到一個 Register，將它的現在時間加上原本頻率再度 push 回...

# 題目: UVa 12207 - That is Your Queue # 題目說明 政府終於解決了全民健保問題，而建立了一套系統 你需要用程式寫這個系統，說明如下: 每個人被分配到一個編號，由 1 開始排 當緊急狀況發生時，會有人優先移到前面 INPUT: 每筆測資第一行有兩個整數 P 和 C ， P 代表國家的人口數， C 代表接下來的指令數 (當 P 與 C 為 0 時結束程式) 接下來會有 C 行，每行會有 N 或 E x N 代表輸出最前面的人並移動到最後 E x 代表將編號為 x 的人移動到最前面 OUTPUT: 每遇到 N ，輸出最前面的人 # 解題方法 利用...