f339 - 3.下雪的日子(Snow)
題目描述
題目給定道路總長度 N 和暢通道路區間的資訊，要求找出所有被雪覆蓋的道路區間，並按照區間左界由小到大輸出。
解題思路
這題的核心思想是遍歷整個道路，並利用一個布林陣列 a 記錄每個路段是否暢通。對於每個被雪覆蓋的區間，找到連續的被覆蓋路段，並輸出其左右端點。使用貪心策略，每次從當前位置開始尋找下一個連續的暢通路段，並輸出中間的被覆蓋路段。
複雜度分析
- 時間複雜度: O(N + M)，其中 N 是道路總長度，M 是暢通道路區間的數量。遍歷道路需要 O(N) 時間，處理每個暢通區間需要 O(M) 時間。
- 空間複雜度: O(N)，主要用於儲存布林陣列
a，記錄每個路段是否暢通。
程式碼
#include <iostream>
using namespace std;
bool a[100001];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,m,x,y,s=0;
cin >> n >> m;
while(m--){
cin >> x >> y;
for(int i=x;i<y;++i)
a[i]=1;
}
while(s<n){
int k=s;
while(a[k]==0&&k<n)
++k;
if(k!=s)
cout << s << " " << k << "\n";
s=max(s+1,k);
}
}