ZeroJudge 解題筆記：f632. 渡船頭

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


ZeroJudge 題目連結：f632. 渡船頭

解題想法

先讀取所有的乘客資料，在結束營業之前到的人才加入串列 passenger 之中，接下來依照時間由小到大排序。另外開一個最大優先佇列，儲存目前乘客會給的小費。再用一個 for 迴圈依序産生出發時刻，讀取當時已到站的乘客資料，將乘客會給的小費存入 pq 之中；再從 pq 取出資料加到利潤 profit 之中，直到 pq 沒有資料或是這趟人數到達上限為止。

Python 程式碼

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

import sys, heapq

t1, t2, k, p = map(int, sys.stdin.readline().split())  # 營業時間，間距，每趟人數
passenger = []  # 乘客到站時間、小費
for line in sys.stdin:  # 讀取資料直到 EOF 為止
    if line.strip() == "": continue  # 如果讀到空行，找下一行
    t, m = map(int, line.split())  # 這個乘客的到站時間、小費
    if t <= t2: passenger.append((t, m))  # 在結束營業之前到的人才加入
passenger.sort()  # 依照時間排序
tot, profit, idx, n = 0, 0, 0, len(passenger)  # 總載客人數，總收入，從 passenger 讀資料的索引值，人數
pq = []  # 存入目前乘客小費的優先佇列
for dep in range(t1, t2+1, k):  # 依序産生出發時刻
    while idx < n:  # 如果 idx 還沒有出界繼續執行
        t, m = passenger[idx]  # 到站時間、小費
        if t <= dep: heapq.heappush(pq, -m)  # 如果 t 小於等於發車時刻，m 加負號再加入 pq
        else: break  # 否則中止迴圈
        idx += 1  # idx 加 1
    cnt = 0  # 這趟已載人數
    while pq and cnt < p:  # 如果 pq 還有資料而且還沒有載滿
        profit += -heapq.heappop(pq)  # 從 pq 讀取並移除首項，轉為正值加到 profit
        cnt += 1; tot += 1  # 更新人數
print(tot, profit)  # 印出答案

C++ 程式碼

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

#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int t1, t2, k, p;  // 營業時間，間距，每趟人數
    scanf("%d %d %d %d", &t1, &t2, &k, &p);
    vector<pair<int, int>> passenger;  // 乘客到站時間、小費
    int t, m;  // 這個乘客的到站時間、小費
    while(scanf("%d %d", &t, &m) != EOF) {
        if (t <= t2) passenger.push_back(make_pair(t, m));  // 在結束營業之前到的人才加入
    }
    sort(passenger.begin(), passenger.end());  // 依照時間排序
    int tot = 0, profit = 0, idx = 0, n = (int)passenger.size();  // 總載客人數，總收入，從 passenger 讀資料的索引值，人數
    priority_queue<int> pq;  // 存入目前乘客小費的優先佇列
    for(int dep=t1; dep<=t2; dep += k) {  // 依序産生出發時刻
        while(idx < n) {  // 如果 idx 還沒有出界繼續執行
            int time = passenger[idx].first, money = passenger[idx].second;  // 到站時間、小費
            if (time <= dep) pq.push(money);  // 如果 time 小於等於發車時刻，money 加入 pq
            else break;  // 否則中止迴圈
            idx++;  // idx 加 1
        }
        int cnt = 0;  // 這趟已載人數
        while(!pq.empty() && cnt < p) {  // 如果 pq 還有資料而且還沒有載滿
            profit += pq.top(); pq.pop();  // 從 pq 讀取並移除首項，轉為正值加到 profit
            cnt++; tot++;  // 更新人數
        }
    }
    printf("%d %d\n", tot, profit);  // 印出答案
    return 0;
}