ZeroJudge 解題筆記：e796. p3. 站牌廣告

作者：王一哲
日期：2025年1月31日



ZeroJudge 題目連結：e796. p3. 站牌廣告

解題想法

因為測資範圍不太，在找人流最大值、最小值的站牌編號用線性搜尋，從頭到尾掃過一次即可，效率並不差。

Python 程式碼

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

B = int(input())  # 站牌數量，站牌編號 1 ~ B
P = int(input())  # 人數
cnt = [0]*(B+1)  # 各站牌人流，左端加上一格
for _ in range(P):  # 讀取 P 行資料
    u, v = map(int, input().split())  # 上車、下車站牌編號
    if u > v: u, v = v, u  # 如果 u 大於 v，兩者交換
    for i in range(u, v+1): cnt[i] += 1  # 更新 [u, v] 之間的人流
imax, imin = 0, P+1  # 人流最大值、最小值
pmax, pmin = 0, 0  # 人流最大值、最小值的站牌編號
for i in range(1, B+1):  # 依序檢查站牌 1 ~ B
    if cnt[i] >= imax:  # 如果 cnt[i] 大於等於 imax
        imax = cnt[i]  # 更新 imax
        pmax = i  # 更新 pmax
    if cnt[i] < imin:  # 如果 cnt[i] 小於 imin
        imin = cnt[i]  # 更新 imin
        pmin = i  # 更新 pmin
print(f"{pmin:d} {pmax:d}")  # 印出答案

也可以用 min、max 及串列切片找位置。使用時間約為 70 ms，記憶體約為 3.3 MB，通過測試。

B = int(input())  # 站牌數量，站牌編號 1 ~ B
P = int(input())  # 人數
cnt = [0]*(B+1)  # 各站牌人流，左端加上一格
for _ in range(P):  # 讀取 P 行資料
    u, v = map(int, input().split())  # 上車、下車站牌編號
    if u > v: u, v = v, u  # 如果 u 大於 v，兩者交換
    for i in range(u, v+1): cnt[i] += 1  # 更新 [u, v] 之間的人流
pmin = cnt[1:].index(min(cnt[1:])) + 1
pmax = B - cnt[::-1].index(max(cnt[::-1]))
print(f"{pmin:d} {pmax:d}")  # 印出答案

C++ 程式碼

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

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int B; cin >> B;  // 站牌數量，站牌編號 1 ~ B
    int P; cin >> P;  // 人數
    int cnt[B+1] = {0};  // 各站牌人流，左端加上一格
    for(int i=0; i<P; i++) {  // 讀取 P 行資料
        int u, v; cin >> u >> v;  // 上車、下車站牌編號
        if (u > v) {  // 如果 u 大於 v，兩者交換
            int t = u;
            u = v;
            v = t;
        }
        for(int j=u; j<=v; j++) cnt[j]++;  // 更新 [u, v] 之間的人流
    }
    int imax = 0, imin = P+1, pmax = 0, pmin = 0;  // 人流最大值、最小值；人流最大值、最小值的站牌編號
    for(int i=1; i<=B; i++) {  // 依序檢查站牌 1 ~ B
        if (cnt[i] >= imax) {  // 如果 cnt[i] 大於等於 imax
            imax = cnt[i];  // 更新 imax
            pmax = i;  // 更新 pmax
        }
        if (cnt[i] < imin) {  // 如果 cnt[i] 小於 imin
            imin = cnt[i];  // 更新 imin
            pmin = i;  // 更新 pmin
        }
    }
    cout << pmin << " " <<  pmax << "\n";  // 印出答案
    return 0;
}

使用 vector, algorithm, min_element, max_element，反而比較慢。使用時間約為 11 ms，記憶體約為 368 kB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int B; cin >> B;  // 站牌數量，站牌編號 1 ~ B
    int P; cin >> P;  // 人數
    vector<int> cnt (B+1, 0);  // 各站牌人流，左端加上一格
    for(int i=0; i<P; i++) {  // 讀取 P 行資料
        int u, v; cin >> u >> v;  // 上車、下車站牌編號
        if (u > v) swap(u, v);  // 如果 u 大於 v，兩者交換
        for(int j=u; j<=v; j++) cnt[j]++;  // 更新 [u, v] 之間的人流
    }
    int pmin = min_element(cnt.begin()+1, cnt.end()) - cnt.begin();
    int pmax = B - (max_element(cnt.rbegin(), cnt.rend()) - cnt.rbegin());
    cout << pmin << " " <<  pmax << "\n";  // 印出答案
    return 0;
}