ZeroJudge 解題筆記：f339. 3.下雪的日子(Snow)

作者：王一哲
日期：2025年3月3日



ZeroJudge 題目連結：f339. 3.下雪的日子(Snow)

解題想法

有兩個要特別注意的地方：

1. Python 才有的問題，輸入的資料可能是長度等於 1 的字串，要跳過這些字串不處理。
2. 暢通的道路資料可能起點、終點相同，要跳過這些資料不處理。

Python 程式碼

使用時間約為 25 ms，記憶體約為 4.4 MB，通過測試。

import sys
from functools import cmp_to_key

def mycmp(a, b):  # 依照起點由小到大排序，若起點相同，依照終點由大到小排序
    if a[0] < b[0]: return -1
    elif a[0] > b[0]: return 1
    else:
        if a[1] > b[1]: return -1
        elif a[1] < b[1]: return 1
        else: return 0
        
for line in sys.stdin:
    if len(line) <= 1: continue  # 如果字串長度小於等於 1，繼續讀下一行
    n, m = map(int, line.split())  # 道路總長度 n， m 筆道路資訊
    pa = [list(map(int, input().split())) for _ in range(m)]  # 暢通道路
    pa.sort(key = cmp_to_key(mycmp))  # 排序
    ans = []  # 答案
    if pa[0][0] > 0: ans.append((0, pa[0][0]))  # 檢測第0段及 0 之間是否不通
    ri = pa[0][1]  # 目前檢測的右端點
    for s, e in pa[1:]:  # 由 pa[1] 開始依序讀取暢通道路起點 s、終點 e
        if s == e: continue  # 如果 s 等於 e，沒用的資料，繼續找下一段
        if s > ri: ans.append((ri, s))  # 如果 s 大於 ri，中間有不通的地方，(ri, s) 加入 ans
        ri = max(ri, e)  # 更新 ri，取 ri 及 e 較大者
    if n > ri: ans.append((ri, n))  # 最後的右端點與 n 之間不通
    if ans:  # 如果 ans 有內容才印出 ans
        for a in ans: print(*a)

C++ 程式碼

使用時間約為 2 ms，記憶體約為 360 kB，通過測試。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;  // 道路總長度 n， m 筆道路資訊
    while(cin >> n >> m) {
        vector<pair<int, int>> pa (m);  // 暢通道路
        for(int i=0; i<m; i++) cin >> pa[i].first >> pa[i].second;
        sort(pa.begin(), pa.end(), [] (pair<int, int> a, pair<int, int> b) {
            if (a.first == b.first) return a.second > b.second;
            else return a.first < b.first; } );  // 依照起點由小到大排序，若起點相同，依照終點由大到小排序
        vector<pair<int, int>> ans;  // 答案
        if (pa[0].first > 0) ans.push_back(make_pair(0, pa[0].first));  // 檢測第0段及 0 之間是否不通
        int ri = pa[0].second;  // 目前檢測的右端點
        for(int i=1; i<m; i++) {  // 由 pa[1] 開始依序讀取暢通道路起點 s、終點 e
            int s = pa[i].first, e = pa[i].second;
            if (s == e) continue;  // 如果 s 等於 e，沒用的資料，繼續找下一段
            if (s > ri) ans.push_back(make_pair(ri, s));  // 如果 s 大於 ri，中間有不通的地方，(ri, s) 加入 ans
            ri = max(ri, e);  // 更新 ri，取 ri 及 e 較大者
        }
        if (n > ri) ans.push_back(make_pair(ri, n));  // 最後的右端點與 n 之間不通
        if (!ans.empty()) {  // 如果 ans 有內容才印出 ans
            for(auto a : ans) cout << a.first << " " << a.second << "\n";
        }
    }
    return 0;
}