ZeroJudge 解題筆記：f631. 同學會

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


ZeroJudge 題目連結：f631. 同學會

解題想法

這題要用最大優先佇列儲存每個人目前有的錢，由於 Python 的 heapq 是最小優先佇列，要將每一筆資料都加上負號。

Python 程式碼

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

import sys, heapq

for line in sys.stdin:  # 繼續執行直到 EOF 為止
    if line.strip() == "": continue  # 遇到空行，找下一行
    n, m = map(int, line.split())  # n 個人，m 道菜
    money = list(map(int, sys.stdin.readline().split()))  # 每個人原來的錢
    dishes = list(map(int, sys.stdin.readline().split()))  # 每道菜的價格
    if sum(money) < sum(dishes):  # 所有人帶的錢小於所有菜的總價
        print("Oh My God")  # 印出 Oh My God
        continue  # 讀下一筆資料
    pq = [-m for m in money]  # 將 money 每一筆資料加負號存入 pq
    heapq.heapify(pq)  # pq 轉成最小優先佇列
    imax = -pq[0]  # 初始金額最大值
    for dish in dishes:  # 依序讀取每道菜的價格
        while pq and dish > 0:  # 當 pq 還有資料而且 dish 大於 0 時繼續執行
            m = -heapq.heappop(pq)  # 取出 pq 第一項加負號，變回正值
            if m > dish:  # 如果付完這道菜還有錢
                heapq.heappush(pq, -(m-dish))  # 剩下的錢加負號，存入 pq
                dish = 0  # 待付金額為 0
            elif m == dish: dish = 0  # 如果這個人的錢剛好夠用，待付金額為 0
            else: dish -= m  # 如果這個人的錢不夠，更新待付金額
    print(imax, -pq[0] if pq else 0)  # 印出 imax，如果 pq 有資料印出 -pq[0]，反之印出 0

C++ 程式碼

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

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int n, m;  // n 個人，m 道菜
    while(scanf("%d %d", &n, &m) != EOF) {
        int sum_money = 0;  // 所有人帶的錢
        priority_queue<int> pq;  // 每個人原來的錢
        for(int i=0, money; i<n; i++) {
            scanf("%d", &money);
            pq.push(money);
            sum_money += money;
        }
        int dishes[m], sum_dish = 0;  // 每道菜的價格，所有菜的總價
        for(int i=0, dish; i<m; i++) {
            scanf("%d", &dish);
            dishes[i] = dish;
            sum_dish += dish;
        }
        if (sum_money < sum_dish) {  // 所有人帶的錢小於所有菜的總價
            printf("Oh My God\n");  // 印出 Oh My God
            continue;  // 讀下一筆資料
        }
        int imax = pq.top();  // 初始金額最大值
        for(int i=0; i<m; i++) {  // 依序讀取每道菜的價格
            int dish = dishes[i];
            while(!pq.empty() && dish > 0) {  // 當 pq 還有資料而且 dish 大於 0 時繼續執行
                int money = pq.top(); pq.pop();  // 取出 pq 第一項
                if (money > dish) {  // 如果付完這道菜還有錢
                    pq.push(money-dish);  // 剩下的錢加負號，存入 pq
                    dish = 0;  // 待付金額為 0
                } else if (money == dish) {  // 如果這個人的錢剛好夠用，待付金額為 0
                    dish = 0;
                } else {  // 如果這個人的錢不夠，更新待付金額
                    dish -= money;
                }
            }
        }
        // 印出 imax，如果 pq 有資料印出 pq.top()，反之印出 0
        if (!pq.empty()) printf("%d %d\n", imax, pq.top());
        else printf("%d 0\n", imax);
    }
    return 0;
}

使用時間約為 0.3 s，記憶體約為 424 kB，通過測試。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;  // n 個人，m 道菜
    while(cin >> n >> m) {
        int sum_money = 0;  // 所有人帶的錢
        priority_queue<int> pq;  // 每個人原來的錢
        for(int i=0, money; i<n; i++) {
            cin >> money;
            pq.push(money);
            sum_money += money;
        }
        int dishes[m], sum_dish = 0;  // 每道菜的價格，所有菜的總價
        for(int i=0, dish; i<m; i++) {
            cin >> dish;
            dishes[i] = dish;
            sum_dish += dish;
        }
        if (sum_money < sum_dish) {  // 所有人帶的錢小於所有菜的總價
            cout << "Oh My God\n";  // 印出 Oh My God
            continue;  // 讀下一筆資料
        }
        int imax = pq.top();  // 初始金額最大值
        for(int i=0; i<m; i++) {  // 依序讀取每道菜的價格
            int dish = dishes[i];
            while(!pq.empty() && dish > 0) {  // 當 pq 還有資料而且 dish 大於 0 時繼續執行
                int money = pq.top(); pq.pop();  // 取出 pq 第一項
                if (money > dish) {  // 如果付完這道菜還有錢
                    pq.push(money-dish);  // 剩下的錢加負號，存入 pq
                    dish = 0;  // 待付金額為 0
                } else if (money == dish) {  // 如果這個人的錢剛好夠用，待付金額為 0
                    dish = 0;
                } else {  // 如果這個人的錢不夠，更新待付金額
                    dish -= money;
                }
            }
        }
        // 印出 imax，如果 pq 有資料印出 pq.top()，反之印出 0
        cout << imax << " " << (!pq.empty() ? pq.top() : 0) << "\n";
    }
    return 0;
}