# 2023 交大電機營 C++ 進階題題解
---
## **Problem 1.** 超躁的電機營工人
### 想法解析
:::info
如果我們直接暴力列舉，去更新每個時間點每個人的位置和行走方向，執行的複雜度會為 **O(nt)** ，以這題的測資大小來說時間長跟人數都會到達 10^7^ ，總共的時間複雜度就大約 10^14^ ，遠超過電腦一秒能執行大約 10^8^ 步的限制。因此，這種暴力列舉的解法是一定不行的!
在獨木橋上的各個電機營工人們不斷的相撞轉向。但是如果我們不管人是誰，只管獨木橋上人的分布情形，我們可以發現，其實如果把每個相撞轉向的情形都視作兩個人可以直接交錯穿過，獨木橋上人的分布跟行走情形會跟有相撞轉向的情形一樣。
利用這個性質，在得到每個人的初始輸入資料後，我們把他視作直接向他的原始方向走，不進行任何相撞轉向，這樣檢查一個人會不會在 **t** 秒後還在獨木橋上就只需要檢查他的位置跟他要前往的獨木橋尾端距離，這樣檢查一個人所需的時間複雜度就只有 **O(1)** ，計算所有人的情形，總共需要的時間複雜度就是 **O(n)** ，為在一秒內執行得完的時間複雜度。
:::
### **Solution Code**
:::success
- **Time Complexity: O(n)**
- **Space Complexity: O(1)**
:::
```C++=
#include <iostream>
using namespace std;
int main() {
int people_num, length, time;
cin >> length >> people_num >> time;
int count = people_num;
for (int i = 0; i < people_num; i++) {
int pos;
char dir;
cin >> pos >> dir;
if (dir == 'L' && pos < time) count--;
else if (dir == 'R' && pos+time > length) count--;
}
cout << count << '\n';
return 0;
}
```
---
## **Problem 2.** 喔不! 要遲到啦!!
### 想法解析
:::info
(如果不知道二分搜尋法的小隊員們想學這題，要上網查一下 binary search 喔!)
我們知道答案(也就是ㄅㄚˊㄌㄚˋ能用的最慢速度) 最大是 **10^7^ m/min**，用二分搜尋法掃過整個答案的值域，並且檢查該速度 **V** 是否是我們要求的答案。檢查方式就是確認該速度是可以準時抵達的，如果速度減一過後會導致遲到，那該速度就是他能用的最慢速度。如果連該速度都會遲到，代表速度太慢；如果連速度減一過後都還會準時，就代表速度過快。
檢查一次的方法，我們需要將每個點之間的距離除上速度後加總，得到最後花的總時長。如此檢查一次所需的時間複雜度為 **O(n)**。
特別注意一定會遲到的情形可以直接判定喔!
搭配上二分搜尋法的檢查得到最後的答案，總共花的時間複雜度為 **O(nlogV)**，執行步數量級大約在 **10^6^** 至 **10^7^**
:::
### **Solution Code**
:::success
- **Time Complexity: O(nlogV)**
- **Space Complexity: O(n)**
:::
```C++=
#include <iostream>
#include <vector>
using namespace std;
bool check (int sp, const vector<int>& dist, double hour) {
double cnt = 0;
for (size_t i = 0; i < dist.size()-1; i++) {
if (dist[i] % sp) cnt += dist[i]/sp+1;
else cnt += dist[i]/sp;
}
cnt += (1.0*dist[dist.size()-1])/sp;
return cnt <= hour;
}
int minSpeedOnTime(const vector<int>& dist, double hour) {
int upper = 1e7, lower = 1;
if (!check(upper, dist, hour)) return -1;
int mid;
while (upper >= lower) {
mid = (upper+lower)/2;
if (check (mid, dist, hour)) upper = mid-1;
else lower = mid+1;
}
return lower;
}
int main() {
int n;
vector<int> dist;
double hour;
cin >> n >> hour;
dist = vector<int> (n, 0);
for (int i = 0; i < n; i++) cin >> dist[i];
cout << minSpeedOnTime (dist, hour);
return 0;
}
```
---
## **Problem 3. King of EECamp**
### 想法解析
:::info
這題因為有限制空間複雜度必須為 **O(m)**，也就是說我們存取資料所用到的空間大小只能是 ***m*** 的量級大小。
觀察這題競技場中的規則機制，我們可以發現最後停留在競技場上的小隊員，他們的能力值跟編號其實具有單調性。
因為新的小隊員進入戰場後，會先淘汰掉所有能力值比他低的人，因此經過這個操作，新加入競技場的小隊員必定會是此刻留在場上中能力值最低的。
而此刻還留在場上且是最早進入競技場的小隊員，必定會是在此刻競技場上能力值最高的人，因為後續的其他人都沒有把他淘汰，也就是能力值沒有比他高。
我們使用 ***雙向佇列 (deque)*** 這種資料結構作存取跟操作
因此在每一輪有小隊員要從佇列後端新加入時，只須由後往前檢查，淘汰掉所有能力值比他低的人，而檢查到一個比他強的人之後，其他更前面的人必定都會比他強。
那如果該輪新加入的小隊員無法淘汰人，而導致競技場上人數過多時，我們要找的最強的人，其實就直接是我們雙向佇列中的第一個人。
由上面的作法，
我們最多會對每個人進行一次 push 跟 pop ，因此總共的時間複雜度為 **O(n)**
而空間複雜度的部分，因為我們會在雙向佇列超過 ***m*** 個人時把最強的人移除，雙向佇列始終都是維持在 ***m*** 的大小。因此空間複雜度有達成題目 **O(m)** 的要求。
:::
### **Solution Code**
:::success
- **Time Complexity: O(n)**
- **Space Complexity: O(m)**
:::
```C++=
#include <iostream>
#include <deque>
using namespace std;
bool less (const pair<int, int> &a, const pair<int, int> &b) {
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
}
int main() {
int n, m;
cin >> n >> m;
deque<pair<int, int>> arr;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
bool flag = false;
cout << "Round " << i+1 << " : ";
while (arr.size() > 0 && arr[arr.size()-1].first < num) {
cout << arr[arr.size()-1].second << ' ';
arr.pop_back();
flag = true;
}
if (!flag && arr.size() >= m) {
cout << arr[0].second << ' ';
arr.pop_front();
}
cout << '\n';
arr.push_back ({num, i+1});
}
while (arr.size() > 0) {
cout << arr[arr.size()-1].second << ' ';
arr.pop_back();
}
return 0;
}
```
---
## **Problem 4.** 組出遊前肯定得先學會游泳的吧!
### 想法解析
#### **解法 1. Disjoint Set**
:::info
(先備演算法: :label: disjoint set)
我們使用 **DSU** ，將所有已經連通的區塊併入同一格併查集後，檢查兩個區塊是不是在同一個併查集中就可以得知兩個區塊是否連通。
作法:
每當 ***t*** 增加一，我們就把新的有水區塊與周遭本來有水的區塊的併查集合併，接著檢查起點與終點是否在同一個併查集中，如果是的話，當下的時間 ***t*** 就是我們要求的最快時間。
接著討論時間複雜度，有寫好路徑壓縮的 **DSU**，進行 ```find``` 與 ```union``` 的時間複雜度為 **O(log^\*^n^2^)**，其中 **log\*** 為 **iterated logarithm** 函數，他隨參數的成長速度遠小於一般的 **log**。
計算總共的時間複雜度，因為總共最多會需要過 **n^2^** 的時間才會有結果，所以總共的時間複雜度為 **O(n^2^log^\*^n^2^)**
:::
#### **解法 2. Binary Search**
:::info
(先備演算法: :label: binary search :label: DFS/BFS)
我們可以用二分搜尋法掃過整個答案存在的值域，並用類似第二題的方法檢查是否是最快可以完成的時間。
檢查的方法可以用 ***DFS*** 檢查當下的泳池水深是否可以讓海螺跟猛毒游到右下角的終點。這樣一次檢查的時間複雜度就是 **O(n^2^)**
再乘上二分搜尋法的時間，總共的時間複雜度就是 **O(n^2^logn^2^)**
:::
### **Solution Code**
#### **解法1. Disjoint Set**
:::success
- **Time Complexity: O(n^2^log^\*^n^2^)**
- **Space Complexity: O(n^2^)**
:::
```C++=
#include <iostream>
#include <vector>
using namespace std;
vector<int> root;
bool check (int x, int y, int val, const vector<vector<int>>& grid) {
if (x < 0 || y < 0 || x >= grid.size() || y >= grid.size()) return false;
return grid[x][y] < val;
}
int fnd_root (int x) {
if (root[x] == x) return x;
return root[x] = fnd_root(root[x]);
}
void merge (int x, int y) {
int px, py;
px = fnd_root (x), py = fnd_root (y);
if (px != py) root[px] = py;
}
int swimInWater(const vector<vector<int>>& grid, const vector<int> num) {
int gsz = grid.size();
root = vector<int> (grid.size()*grid.size());
for (size_t i = 0; i < gsz*gsz; i++) root[i] = i;
for (int i = 0; i < gsz*gsz; i++) {
int x, y;
x = num[i] / gsz;
y = num[i] % gsz;
if (check (x+1, y, i, grid)) merge (grid[x+1][y], grid[x][y]);
if (check (x-1, y, i, grid)) merge (grid[x-1][y], grid[x][y]);
if (check (x, y+1, i, grid)) merge (grid[x][y+1], grid[x][y]);
if (check (x, y-1, i, grid)) merge (grid[x][y-1], grid[x][y]);
if (fnd_root(grid[0][0]) == fnd_root (grid[gsz-1][gsz-1])) return i;
}
return -1;
}
int main() {
vector<int> num;
vector<vector<int>> grid;
int grid_size;
cin >> grid_size;
grid = vector<vector<int>> (grid_size, vector<int> (grid_size, 0));
num = vector<int> (grid_size * grid_size, 0);
for (int i = 0; i < grid_size; i++) {
for (int j = 0; j < grid_size; j++) {
cin >> grid[i][j];
num[grid[i][j]] = i * grid_size + j;
}
}
cout << swimInWater (grid, num) << '\n';
return 0;
}
```
#### **解法2. Binary Search**
下面的程式是一題相同觀念的類似題用 binary search 解的解法程式碼，要套用到這題的話要微調一下喔~
:::success
- **Time Complexity: O(n^2^logn^2^)**
- **Space Complexity: O(n^2^)**
:::
```C++=
class Solution {
public:
// Binary search on answer
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n;
bool dfs(int x,int y, int t,vector<vector<int>> &grid, vector<vector<int>> &visit){
visit[x][y]=1;
if(t< grid[x][y]) return false;
if(x== n-1 && y== n-1){
return true;
}
bool an=false;
for(int i=0;i<4;i+=1){
int nx= x + dx[i];
int ny= y + dy[i];
if(nx>=0 && ny>=0 && nx<n && ny<n && grid[nx][ny]<=t && !visit[nx][ny]){
if(nx== n-1 && ny == n-1){
an=true;
}else{
an = an | dfs(nx,ny,t,grid, visit);
}
}
}
return an;
}
int swimInWater(vector<vector<int>>& grid) {
n= grid.size();
int lo=0,hi=1e5;
while(lo<hi){
int mid= lo + (hi-lo)/2;
vector<vector<int>> visit(n+1, vector<int> (n+1,0));
if(dfs(0,0,mid,grid,visit)){
hi=mid;
}else{
lo=mid+1;
}
}
return hi;
}
};
```
:::warning
**Solution 2 code reference -** [leetcode778_binary_search_solution](https://leetcode.com/problems/swim-in-rising-water/solutions/3648900/c-easily-understandable-binary-search-on-answer/)
:::
Sign in with Wallet
Connect another wallet