2024 交大電機營 C++ 進階題

這裡的題目會要多想一下，用到一些資料結構、演算法喔~
如果你真的覺得你語法都會了，一般的C++練習完全難不倒你的話，再來挑戰一下吧!
加油!!

problem 1. 超躁的電機營工人

題目敘述

在一座長度為 L 的獨木橋上有 N 位電機營工人, 給定每個人的初始位置及初始方向(L為左, R為右), 每個人會以每秒 1 單位的速度往初始方向行走。

當跟另一個人面對面相遇時, 因為橋太窄了兩個人不能交錯後各自繼續向前，而且今天電機營工人都很躁，兩個工人相遇時，會相撞打架並同時轉向 （打架不花時間)。請問 T 秒後還有幾個電機營工人在獨木橋上?

( *註:兩個工人有同樣的出發位置及初始方向時, 他們是一起前進的好基友, 但撞到一個對向的工人時,兩個好基友中只有一個人會轉向 )

---

Input

​​​​L N T           //獨木橋長度 初始工人數 經過時常
​​​​pos_1  dir_1
​​​​pos_2  dir_2    //每個工人的初始位置及方向
​​​​...
​​​​pos_n  dir_n
​​​​
​​​​=================================================
​​​​Input constraints -
​​​​
​​​​  1 <= L <= 10^7
​​​​  0 <= N <= L
​​​​  0 <= T <= L

Output

​​​​x        //t秒後還在獨木橋上的電機營工人數

---

Sample testcase

​​​​Input -
​​​​10 5 3  
​​​​3 R
​​​​8 R
​​​​4 L
​​​​6 L
​​​​9 L
​​​​
​​​​Output -
​​​​4

• time constraint: 1s

category:

greedy
reference - #Teleporting Ants

---

problem 2. 喔不 ! 要遲到啦 !!

題目敘述

營期的某一天，課程長 內捲pasta 睡過頭啦

他很急因為他快遲到了!! 還剩 t 分鐘就到集合時間了 ( t 可為浮點數)，內捲pasta 很急因為他不想因為遲到被罰錢，可是他中途還要依序經過 n 個地點，各個點之間的距離會給在一個整數陣列 dist 中，其中 dist[i] 即為第 i 到第 i+1 的點之間的距離

( dist[0] : 宿舍到第一個地點的距離，dist[n-1] : 最後一個地點到集合地的距離)

另外 內捲pasta 有個怪癖，他一定只在整數分鐘的時候離開一個地點。

舉例來說，
如果到達第一個地點的時刻為 1.5 分鐘，內捲pasta 會在那裏等待 0.5 分鐘直到 2 分鐘的時刻才出發前往第二個地點。
如果到達第二個地點的時刻恰巧為第 3 分鐘，內捲pasta 會馬上出發前往第三個地點。

內捲pasta 很懶，請你輸出在不遲到的前提下，內捲pasta 能用的最慢速率是多少? (m/min) (每段路程 內捲pasta 的速率固定)
如果一定會遲到的話，輸出 -1

(註 : 題目測資產生的結果會讓答案至多為 10^7)

---

Input

​​​​n t    //總共有幾段路程    還有多久集合
​​​​dist[0] dist[1] ... dist[n-1]    //每段路程的長度
​​​​
​​​​=================================================
​​​​Input constraints -
​​​​  
​​​​  1 <= n <= 10^5
​​​​  1 <= t <= 10^9
​​​​  1 <= dist[i] <= 10^5

Output

​​​​輸出能夠不遲到的最低速率
​​​​(一定遲到的話輸出-1)

---

Sample testcase

​​​​- Sample Input 1 -
​​​​3 2.7
​​​​1 3 2
​​​​
​​​​- Sample Output 1 -
​​​​3
​​​​
​​​​====================
​​​​
​​​​- Sample Input 2 -
​​​​3 6
​​​​1 3 2
​​​​
​​​​- Sample Output 2 -
​​​​1
​​​​
​​​​====================
​​​​
​​​​- Sample Input 3 -
​​​​3 1.9
​​​​1 3 2
​​​​
​​​​- Sample Output 3 -
​​​​-1

• time constraint: 1s

category:

binary search
reference - leetcode_1870

---

Problem 3. King of EECamp

題目敘述

相信每個小隊員參加這次電機營都是為了爭奪 King of EECamp 這個至高無上的稱號，成為本次營隊中最頂尖的王者。

總召要從 n 位小隊員中挑選出本次營隊中最牛逼的小隊員，成為小隊員之間最頂尖的王者。每個人都有自己的能力值 ai，經過無數次慘無人道的廝殺，最終還留在競技場上的那些小隊員就可以成為 King of EECamp

每一輪廝殺中（第 i 輪），會有一位新的小隊員（編號 i ) 進入競技場，新進入的小隊員會把所有已經在場上且能力值比自己低的小隊員淘汰出場。但是由於競技場大小有限制，每一回合結束時，場上最多只能存在 m 個人，如果新加入的小隊員比所有場上的小隊員弱而沒有發起攻擊，且使得競技場上人數超過上限（必定只會超過一人）。此時在競技場上的所有人會一起攻擊當下場上的最強者，使最強者被淘汰。

簡而言之，在第i輪的戰鬥中可以分成三個部分

1. 第 i 個小隊員進入競技場
2. 第 i 個小隊員淘汰掉競技場上能力值比他還低的小隊員
3. 如果沒有人被淘汰，且競技場上的人數超過了限制 m，則最強的小隊員被淘汰
   (當能力值相同時，先進入的因為有經驗所以比較強, 此時會優先被淘汰)

輸入敘述：
第一行有兩個數字 n, m
n 代表總共有幾個小隊員參加競爭
m 代表競技場上最多只能同時存在 m 個人
第二行有 n 個數字，個別代表每個人的能力值

輸出敘述：
輸出有 n+1 行
前 n 行將會是 "Round i: " >> 輸出在第 i 輪被淘汰的小隊員順序編號，中間用空格隔開
第 n+1 行會是 "Final: " >> 輸出最後還留在競技場上小隊員們的編號 （編號遞減）

Input Constraint

​​​​1 <= n <= 10^6         //參加人數
​​​​1 <= m <= 10^3         //競技場人數上線
​​​​1 <= ai <= 10^9        //能力值

---

Sample Testcase

​​​​- Sample Input 1 -
​​​​10 4
​​​​8 5 2 4 7 6 5 3 4 6
​​​​
​​​​- Sample Output 1 -
​​​​Round 1: 
​​​​Round 2: 
​​​​Round 3: 
​​​​Round 4: 3 
​​​​Round 5: 4 2 
​​​​Round 6: 
​​​​Round 7: 
​​​​Round 8: 1 
​​​​Round 9: 8 
​​​​Round 10: 9 7 
​​​​Final: 10 6 5    

​​​​====================
​​​​
​​​​- Sample Input 2 -
​​​​8 3
​​​​5 5 5 5 6 4 4 5
​​​​
​​​​- Sample Output 2 -
​​​​Round 1: 
​​​​Round 2: 
​​​​Round 3: 
​​​​Round 4: 1 
​​​​Round 5: 4 3 2 
​​​​Round 6: 
​​​​Round 7: 
​​​​Round 8: 7 6 
​​​​Final: 8 5 

• time constraint: 1s
  • complexity: O(n), O(nlogn), O(nlogm), O(m^2) are available
  • methods with complexity O(nm), O(n^2) will be too slow
• space complexity constraint: O(m)

category:

data structure
reference - NTU CS >> DSA homework

---

Problem 4. 組出遊前肯定得先學會游泳的吧!

題目敘述

課程組的地縛靈跟艾斯

魔人都不會游泳，作為不會換氣的課程長 內捲pasta 覺得這樣組出遊的時候真的太危險了，因此對他們進行了游泳加強集訓。
經過訓練，發現地縛靈跟艾斯魔人其實都是天賦異稟的游泳高手，在有水的情況下，他們可以在瞬間游到無窮遠的距離。

在日復一日的練習過後，他們終於迎來了最重要的一天 >> 游泳殘酷。
內捲pasta 覺得只是單純游普通泳池太無聊了，精心布置了游泳的殘酷場地，準備了一個底面為 n*n 的方形泳池，對應到一個 n*n 的二維陣列 grid，其中每一格 grid[i][j] 會有一個 0~(n² - 1) 的編號，代表 (i, j) 位置的方格高度。(每個方格的高度不同，編號不會重複)
四邊周遭有高牆可以讓所有的水留在泳池內。

開始殘酷時，地縛靈跟艾斯

魔人從左上角位置 (0, 0) 出發，接著 內捲pasta 開始在泳池放水，經過 t 分鐘後，泳池的水深為 t ，意即當時間過了 t 分鐘後，所有高度低於或等於 t 的方格上都會有水，也就是可以游泳的地方。如果自己所在的區塊有水，他們就可以游到相鄰(上下左右)的有水區塊。

內捲pasta 拿著計時器站在殘酷場地邊，請問地縛靈跟艾斯

魔人最快要多久能游到右下角的終點，完成殘酷，註: 右下角座標為 (n-1, n-1)

---

Input

​​​​n    //泳池底面大小 n*n
​​​​
​​​​grid[0][0]    grid[0][1]    ...     grid[0][n-1]
​​​​grid[1][0]      ...         ...        ...
​​​​   ...          ...         ...        ...
​​​​grid[n-1][0]    ...         ...     grid[n-1][n-1]
​​​​
​​​​=================================================
​​​​Input constraints -
​​​​
​​​​  1 <= n <= 50
​​​​  0 <= grid[i][j] < n^2

Output

​​​​T    //地縛靈跟艾斯雞魔人完成殘酷的最快時間

---

Sample Testcase

​​​​- Sample Input 1 -
​​​​2
​​​​0 2
​​​​1 3
​​​​
​​​​- Sample Output 1 -
​​​​3
​​​​
​​​​== Explanation ==
​​​​At time 0, you are in grid location (0, 0).
​​​​You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
​​​​You cannot reach point (1, 1) until time 3.
​​​​When the depth of water is 3, we can swim anywhere inside the grid.
​​​​
​​​​====================
​​​​- Sample Input 2 -
​​​​5
​​​​0	1	2	3	4
​24	23	22	21	5
​12	13	14	15	16
​11	17	18	19	20
​10	9	8	7	6
​
​
​- Sample Output 2 -
​​​​16
​​​​
​​​​
​​​​== Explanation ==
​​​​final route >>
​​​​0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 16 -> 15 -> 14 -> 13 -> 12 -> 11 -> 10
​​​​-> 9 -> 8 -> 7 -> 6
​​​​
​​​​we need to wait until time 16 so that (0, 0) and (4, 4) are connected.

category:

disjoint set binary search
reference - leetcode_778