課程名稱：資料結構 CS203 A授課教師：林基成發放時間：2020-10-29截止時間：2020-11-05 題目說明這次的作業是 UVa 中的 6 題題目。三題與 Stack 相關，三題與 Queue 相關。 與 Stack 相關 UVa - 514 - Rails：UVa - 514 解題紀錄 UVa - 732 - Anagrams by Stack：UVa - 732 解題紀錄 UVa - 1062 - Containers：UVa - 1062 解題紀錄 與 Queue 相關 UVa - 10172 - The Lonesome Cargo Distributor：UVa - 10172 解題紀錄 UVa - 10901 - Ferry Loading III：UVa - 10901 解題紀錄 UVa - 11034 - Ferry Loading IV：UVa - 11034 解題紀錄

題目： UVa - 11034 - Ferry Loading IV 題目說明有一艘可以載車子的船，兩岸分別有一些要到達對岸的車子，船有長度限制，在不超過船的長度限制的前提下，要放多少輛車都可以。在岸邊的車子有先後順序之分，在載完前面的車子前，不可以載後面的車子。 Input： 第一行為一個整數 T，代表有 T 組測資，每組測資第一行為兩個整數 l, m，分別代表 船的長度 ( 船的長度的單位為車子長度的單位的一百倍 ) 及 需要過岸的車子數量，接下來 m 行，每行有一個整數及一個字串，整數代表車子的長度，字串只會為 "left" 或 "right" 代表車子所在的那個岸邊。 Output： 求將所有車子都移到各自的對岸，船需要走幾趟 ( 來回算兩趟 )。 解題思路使用兩個 Queue 代表左岸及右岸，儲存車子的長度，之後模擬操作即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include < ...

題目： UVa - 10901 - Ferry Loading III 題目說明有一艘可以載車子的船，兩岸分別有一些要到達對岸的車子。船只有一艘，且一開始在左岸，當船目前所在的岸沒有車子，而對岸有車時，船必須直接過去載車，若是兩岸目前都沒有車，則船可以維持不動。而船上只要一有車就必須開到對岸，不可以等後面的車到達才開船。 Input： 第一行為一整數 T，代表有 T 組測資，每組測資第一行為三個整數 n, t, m，分別代表 船上能載的車子最大數量、船從一岸到達另一岸所需要的時間、需要過岸的車子數量。接下來 m 行，每行有一個整數及一個字串，整數代表車子到達岸邊的時間，字串只會為 "left" 或 "right" 代表車子到達的那個岸邊。 Output： 按照 Input 時車子的順序輸出車子到達對岸的時間。每組測資中間需以空行隔開。 解題思路使用兩個 Queue 代表左岸及右岸，存放車子的編號 ( 代表順序 ) 及到達的時間。接著定義 time 為目前的時間，cur 為目前的位置 ( 0 為左岸，1 為右岸 )。每次執行時，先取得兩岸最先到 ...

題目： UVa - 10172 - The Lonesome Cargo Distributor 題目說明有一台卡車及一個環形公路，公路上有許多站點，每個站點會有一個地方放要送到這個站點的貨物，還有一個要到其他站點的 Queue，所有站點的 Queue 都會有相同的容量限制，卡車的結構類似於 Stack，在移除上面的貨物前，無法移動下面的貨物。卡車每到一個站後都會執行相同的事情： 先將車上的貨物卸下，若是目前的站點是貨物要到達的站點的話則直接卸下，否則放入該站點的 Queue 的尾端，重複執行直到貨車為空或是該站點的 Queue 已滿。 將站點的 Queue 中的貨物從前端開始放到卡車上，直到卡車滿或是 Queue 為空。 移動到下一個站點。 重複以上的動作直到所有貨物都到達該到達的站點為止。 卡車每次卸貨或裝貨都會花費一分鐘。 卡車每次移動到下個站點都會花費兩分鐘。 Input： 第一行為一整數，代表接下來有幾組測資。每組測資的第一行有三個整數 n、s、q，分別代表 站點的數量、貨車的最大容量、站點中 Queue 的最大容量。接下來會有 n 行，代表站點的資訊，從第一個站 ...

題目： UVa - 1062 - Containers 題目說明給一個字串，代表依序進到港口的貨物，後面的貨物進來後就無法再移動前面的貨物，在港口的貨物須從下而上按照字典序的大而小排序，求最少堆成幾堆可以滿足條件。 解題思路解法一： 將港口的每堆貨物視為一個 Stack，每次貨物進來後先檢查能否放在原本的 Stack 上，若無法則新增一個 Stack 後放入。最後輸出 Stack 的個數即可。 解法二： 延續解法一的想法，可以發現由左到右的 Stack 的 top() 其實就是 LIS，所以 Stack 的數量即為 LIS ( 最長嚴格遞增子陣列 ) 的長度，使用 DP 找出長度即可。 參考解法解法一： 123456789101112131415161718192021222324252627282930313233343536#include <iostream>#include <vector>#include <string>#include <stack>#include <functional>using nam ...

題目： UVa - 732 - Anagrams by Stack 題目說明給兩個字串，str、target，求 str 透過 Stack 的 push() 及 pop() 後能否轉換成 target，若可以則輸出所有能達成的操作順序。 解題思路使用 DFS 即可，對於每層 DFS，可以 push() 進 Stack 也可以 pop() 出 Stack，先直接 push() 並往下執行，接著判斷，若 Stack 的 top() 等於當前檢查到的字元則 pop() 並往下執行。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <iostream>#include <string>#include <stack>#include <functional>using namespace std;static auto __ = []{ ios_base::sync_with_ ...

題目： UVa - 514 - Rails 題目說明給一個整數 n，代表有 1, 2, ..., n 個火車，每個火車入站可以直接出站或是等後面的火車入站並出站後再出站，簡單來講就是像 Stack 一樣。給一串數字代表火車出站的順序，若可以達成則輸出 "Yes" 否則輸出 "No"。 解題思路使用 Stack 模擬火車入站出站，使用 Queue 儲存出站順序，若是 Stack 的 top() 與 Queue 的 front() 相同則兩者都不斷 pop()，直到兩者不相同或是 Stack 為空，結束後若 Stack 為空則表示這個順序是可行的。 參考解法1234567891011121314151617181920212223242526272829303132333435#include <iostream>#include <queue>#include <stack>using namespace std;static auto __ = []{ ios_base::sync_with ...

課程名稱：資料結構 CS203 A授課教師：林基成發放時間：2020-10-29截止時間：2020-11-05 題目說明這次的作業是 UVa 中的 5 題題目。兩題與 List 及 Deque 相關，三題與 Priority_queue 相關。 與 List 及 Deque 相關 UVa - 11988 - Broken Keyboard (a.k.a. Beiju Text)：UVa - 11988 解題紀錄 UVa - 12207 - That is Your Queue：UVa - 12207 解題紀錄 與 Priority_queue 相關 UVa - 1203 - Argus：UVa - 1203 解題紀錄 UVa - 10954 - Add All：UVa - 10954 解題紀錄 UVa - 11995 - I Can Guess the Data Structure!：UVa - 11995 解題紀錄

題目： UVa - 11995 - I Can Guess the Data Structure! 題目說明給一個整數 n，代表接下來有 n 行的指令，若指令為 1 加上一個數字，代表將該數字放入容器中，若為 2 加上一個數字，代表容器的 top() 或 front() 為該數字，同時將該數字 pop() 出。結束後判斷該容器為 Stack 或 Queue 還是 Priority_queue，若三者都不是則輸出 "impossible"，若兩者以上的容器皆可則輸出 "not sure"。 解題思路使用三個容器去模擬操作即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <iostream>#include <stack>#include <queue>using namespace std;static auto __ = ...

題目： UVa - 10954 - Add All 題目說明給一些數字，將數字全部相加，相加的過程需要成本，例如 1 + 3 = 4，則成本為 4，求將數字全部相加後的成本為何。 解題思路每次選擇最小的兩者相加即可花費最少的成本。使用 Priority_queue，每次取兩個最小的數字出來相加即可。 參考解法1234567891011121314151617181920212223242526272829303132#include <iostream>#include <queue>using namespace std;static auto __ = []{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();int main(){ int n, tmp; priority_queue<int, vector<int>, greater<int>> pq; whi ...