i401 - 3. 雷射測試
題目描述
題目描述了一個雷射光從 (0,0) 發射，遇到鏡子反射的過程。給定鏡子的位置和擺放方式，要求計算雷射光反射的次數。鏡子的擺放方式用一個參數 t 表示，t=0 表示斜線 /，t=1 表示斜線 \。
解題思路
本題的核心思路是模擬雷射光的路徑。由於雷射光每次遇到鏡子會改變方向，因此需要根據鏡子的擺放方式判斷反射方向。為了避免無限循環，題目保證輸入沒有無限循環的情形。
程式碼使用一個二維 vector a 來儲存每個位置的鏡子資訊。a[i][0] 儲存 x 座標為 i 的鏡子，a[i][1] 儲存 y 座標為 i 的鏡子。程式碼首先將輸入的鏡子資訊儲存到 a 中，然後對每個位置的鏡子進行排序。
模擬過程中，使用 w 變數來表示雷射光目前的行進方向。w=0 表示水平向右，w=1 表示垂直向上，w=2 表示水平向左，w=3 表示垂直向下。程式碼使用 lower_bound 函數在 a 中尋找下一個可能反射的鏡子。如果找到鏡子，則更新雷射光的位置和方向，並增加反射次數。如果找不到鏡子，則結束模擬。
複雜度分析
- 時間複雜度: O(n log n + n log n) = O(n log n)，其中 n 是鏡子的數量。排序鏡子的時間複雜度是 O(n log n)，模擬雷射光路徑的過程中，每次尋找下一個鏡子使用二分搜尋，時間複雜度是 O(log n)，總共需要尋找 n 次鏡子，因此時間複雜度是 O(n log n)。
- 空間複雜度: O(n)，其中 n 是鏡子的數量。空間複雜度主要來自於儲存鏡子資訊的 vector
a。
程式碼
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,x,y,z,w=3,ans;
vector <pair <int,int>> a[60005][2];
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n;
for(int i=0;i<n;++i){
cin >> x >> y >> z;
a[x+30000][0].push_back({y,z});
a[y+30000][1].push_back({x,z});
}
for(int i=0;i<2;++i)
for(int j=0;j<=60000;++j)
sort(a[j][i].begin(),a[j][i].end());
x=y=0;
while(1){
bool out=0;
if(w==0){
int it=lower_bound(a[x+30000][w/2].begin(),a[x+30000][w/2].end(),make_pair(y,2))-a[x+30000][w/2].begin();
if(it>=a[x+30000][w/2].size())out=1;
else{
++ans;
y=a[x+30000][w/2][it].first;
(a[x+30000][w/2][it].second)?w=2:w=3;
}
}
else if(w==1){
int it=lower_bound(a[x+30000][w/2].begin(),a[x+30000][w/2].end(),make_pair(y,0))-a[x+30000][w/2].begin()-1;
if(it<0)out=1;
else{
++ans;
y=a[x+30000][w/2][it].first;
(a[x+30000][w/2][it].second)?w=3:w=2;
}
}
else if(w==2){
int it=lower_bound(a[y+30000][w/2].begin(),a[y+30000][w/2].end(),make_pair(x,0))-a[y+30000][w/2].begin()-1;
if(it<0)out=1;
else{
++ans;
x=a[y+30000][w/2][it].first;
(a[y+30000][w/2][it].second)?w=0:w=1;
}
}
else{
int it=lower_bound(a[y+30000][w/2].begin(),a[y+30000][w/2].end(),make_pair(x,2))-a[y+30000][w/2].begin();
if(it>=a[y+30000][w/2].size())out=1;
else{
++ans;
x=a[y+30000][w/2][it].first;
(a[y+30000][w/2][it].second)?w=1:w=0;
}
}
if(out)break;
}
cout << ans;
}