ZeroJudge 解題筆記：k517. P5.波動 (Wave)

作者：王一哲
日期：2025年5月2日



ZeroJudge 題目連結：k517. P5.波動 (Wave)

解題想法

因為這題需要將所有的波依照傳播的時間由小到大排序，如果時間相同再依照方向 W、S、E、N 排序。如果將時間、方向組成 Python 的 tuple 或是 C++ 的 pair 再排序，但由於 W、S、E、N 不是依照字典順序，不能這樣處理。所以我先將 W、S、E、N 換成對應的數字 0、1、2、3，與時間組成 tuple 再排序，輸出結果時再將數字換回 W、S、E、N。在 C++ 則是自訂結構體，再用 lambda function 自訂排序規則。

Python 程式碼

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

import sys

c2n = {'W': 0, 'S': 1, 'E': 2, 'N': 3}
n2c = ('W', 'S', 'E', 'N')
for line in sys.stdin:
    p = int(line)  # p 道波動
    wave = []  # 傳播時間，波源方位
    for _ in range(p):  # 執行 p 次
        c, d, v = input().split()  # 波源方位，距離，波速
        d = int(d); v = int(v)  # 轉成 int
        wave.append((d/v, c2n[c]))  # (d/v, c2n[c]) 加入 wave
    wave.sort()  # 依照 (t, 方向) 由小到大排序
    print("".join([n2c[n] for _, n in wave]))  # 由 wave 取出 n，換成對應的字母，接成字串，印出

C++ 程式碼

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

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

struct Wave {
    char c;
    double t;
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    map<char, int> c2n = {{'W', 0}, {'S', 1}, {'E', 2}, {'N', 3}};
    int p;  // p 道波動
    while(cin >> p) {
        vector<Wave> waves (p);  // 傳播時間，波源方位
        for(int i=0; i<p; i++) {  // 執行 p 次
            char c; int d, v;  // 波源方位，距離，波速
            cin >> c >> d >> v;
            waves[i].c = c;
            waves[i].t = static_cast<double>(d)/v;
        }
        sort(waves.begin(), waves.end(), [&] (Wave a, Wave b) {  // 依照 (t, 方向) 由小到大排序
             if (a.t == b.t) return c2n[a.c] < c2n[b.c];
             else return a.t < b.t; } );
        for(auto w : waves) cout << w.c;  // 由 wave 取出 n，換成對應的字母，接成字串，印出
        cout << "\n";
    }
    return 0;
}