ZeroJudge 解題筆記：a535. 10141 - Request for Proposal

作者：王一哲
日期：2026年1月8日


ZeroJudge 題目連結：a535. 10141 - Request for Proposal

解題想法

依序掃過所有的廠商資料，如果讀到新的最大商品數量、最低價格，更新贏家名稱。

Python 程式碼

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

import sys

ca = 0
for line in sys.stdin:
    n, p = map(int, line.split())  # 需求表項目數量 n、廠商數量 p
    ca += 1
    if n == 0 and p == 0: break
    for _ in range(n):  # 讀取 n 行資料，解題時用不到
        _ = sys.stdin.readline()
    winner = ""  # 贏家
    price = float('inf')  # 最低價格，預設為最大值
    item = 0  # 廠商提供的商品在需求表中的最大數量
    for _ in range(p):  # 讀取 p 家廠商資料
        name = sys.stdin.readline().rstrip()  # 廠商名稱
        d, r = sys.stdin.readline().split()  # 價格 d、商品數量 r
        d = float(d)  # d 轉成浮點數
        r = int(r)  # r 轉成整數
        if r > item:  # 如果 r 大於 item
            winner = name  # 新的贏家
            price = d  # 新的最低價
            item = r  # 新的商品數量
        elif r == item and d < price:  # 如果商品數量一樣而且價格較低
            winner = name  # 新的贏家
            price = d  # 新的最低價
        for _ in range(r):  # 讀取 r 行資料，解題時用不到
            _ = sys.stdin.readline()
    if ca > 1: sys.stdout.write("\n")
    sys.stdout.write(f"RFP #{ca:d}\n{winner:s}\n")  

C++ 程式碼

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

#include <iostream>
#include <string>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int ca = 0, n, p;  // 第幾個案子，需求表項目數量 n、廠商數量 p
    string s;  // 暫存資料用的字串
    while(cin >> n >> p) {
        if (n == 0 && p == 0) break;
        ca++;
        cin.ignore();  // 等一下要用 getline，要先跳過前一行的 \n
        for(int i=0; i<n; i++) getline(cin, s);  // 讀取 n 行資料，解題時用不到
        string winner = "";  // 贏家
        int price = INT_MAX;  // 最低價格，預設為最大值
        int item = 0;  // 廠商提供的商品在需求表中的最大數量
        for(int i=0; i<p; i++) {  // 讀取 p 家廠商資料
            string name; getline(cin, name);  // 廠商名稱
            float d; cin >> d;  // 價格 d
            int r; cin >> r;    // 商品數量 r
            if (r > item) {  // 如果 r 大於 item
                winner = name;  // 新的贏家
                price = d;  // 新的最低價
                item = r;  // 新的商品數量
            } else if (r == item && d < price) {  // 如果商品數量一樣而且價格較低
                winner = name;  // 新的贏家
                price = d;  // 新的最低價
            }
            cin.ignore();
            for(int i=0; i<r; i++) getline(cin, s);  // 讀取 r 行資料，解題時用不到
        }
        if (ca > 1) cout << "\n";
        cout << "RFP #" << ca << "\n" << winner << "\n";
    }
    return 0;
}