ZeroJudge 解題筆記：k853. P7.直播趕場 (Live)

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



ZeroJudge 題目連結：k853. P7.直播趕場 (Live)

解題想法

採用類似〈APCS實作題2016年3月第3題：線段覆蓋長度〉計算重疊線段厚度的寫法，讀到開始直播時刻厚度加 1，讀到直播結束時刻厚度減 1；假設目前檢查的時間端點為 [start, end+1]，若厚度小於等於螢幕數量，可以觀看的時數加上厚度乘以端點距離，若厚度大於螢幕數量，可以觀看的時數加上螢幕數量乘以端點距離。

Python 程式碼

使用時間約為 1 s，記憶體約為 25.1 MB，通過測試。

import sys

for line in sys.stdin:
    n, s = map(int, line.split())  # n 個螢幕，s 個直播
    cast = []  # 直播開始、結束時刻，開始厚度加 1，結束厚度減 1
    for _ in range(s):  # 讀取 s 行資料
        start, end = map(int, input().split())
        cast += [(start, 1), (end+1, -1)]  # 結束時刻要加 1
    cast.sort()  # 排序
    last = 0  # 正在檢查的範圍開始時刻
    thick = 0  # 厚度，正在直播的頻道數量
    ans = 0  # 答案，可以觀看的直播總時數
    for p, t in cast:  # 依序讀取時刻及厚度變化
        if thick > 0:  # 如果目前直播頻道數量大於 0
            ans += min(thick, n)*(p-last)  # 更新 ans，加上 thick, n 較小值乘以 p-last
        thick += t  # 更新厚度
        last = p  # 更新 last
    print(ans)

C++ 程式碼

使用時間約為 0.2 s，記憶體約為 1.8 MB，通過測試。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
//typedef long long LL;

int main() {
    int n, s;  // n 個螢幕，s 個直播
    while(cin >> n >> s) {
        vector<pair<int, int>> cast (s+s);  // 直播開始、結束時刻，開始厚度加 1，結束厚度減 1
        for(int i=0; i<s+s; i+=2) {  // 讀取 s 行資料
            int start, end; cin >> start >> end;
            cast[i] = make_pair(start, 1);
            cast[i+1] = make_pair(end+1, -1);  // 結束時刻要加 1
        }
        sort(cast.begin(), cast.end());  // 排序
        int last = 0;  // 正在檢查的範圍開始時刻
        int thick = 0;  // 厚度，正在直播的頻道數量
        long ans = 0;  // 答案，可以觀看的直播總時數
        for(int i=0; i<s+s; i++) {  // 依序讀取時刻及厚度變化
            int p = cast[i].first, t = cast[i].second;
            if (thick > 0) {  // 如果目前直播頻道數量大於 0
                ans += min(thick, n)*(p-last);  // 更新 ans，加上 thick, n 較小值乘以 p-last
            }
            thick += t;  // 更新厚度
            last = p;  // 更新 last
        }
        cout << ans << "\n";
    }
    return 0;
}