商品比價 題解｜APCS 2026 年 11 月中級 第 1 題

簡潔題意

\(m\) 家店、\(n\) 項商品。第 \(i\) 家店第 \(j\) 項商品的標價是 \(p_{i,j}\)（\(-1\) 表示沒賣），第 \(i\) 家店全店打 \(d_i\)% off，售價＝標價 \(\times (100 - d_i) / 100\)。每項商品都到售價最便宜的店買，同價選編號最小的店；輸出每項商品到哪家店買，以及買齊的最低總價（\(1 \le m, n \le 50\)；\(p_{i,j} = -1\)，或是 \(0\)～\(50000\) 之間 \(100\) 的倍數；每項商品至少一家店有賣；\(0 \le d_i \le 100\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(60\) 分）：每家店都有賣所有商品（沒有 \(-1\)）。
  • 子題組 2（\(40\) 分）：無額外限制。

先拿下子題組 1（60 分）：售價用整數算，一欄一欄打擂台

先把整張表讀進來。折扣在最後一行，讀完所有標價才知道每家店打幾折，所以先把標價存進二維陣列 p（語法書 6.9）：p[i][j] 是第 \(i\) 家店第 \(j\) 項商品的標價，店號和商品編號都從 \(1\) 開始用，陣列各多開一格（語法書 6.3）。輸入的一行是一家店（表格的一列），所以一項商品是表格的一欄。

售價用整數算。標價是 \(100\) 的倍數，p / 100 一定整除，售價寫成 p / 100 * (100 - d) 就是精確的整數。例如範例 1 店 1 的商品 2：\(200 / 100 \times 80 = 160\)。

不要用小數算，例如 p * (1 - d / 100.0)。\(0.45\)、\(0.67\) 這種小數，電腦只存得下一個很接近的值（\(0.45\) 存的是 \(0.45000000000000001\ldots\)），乘出來就會差一點點。下面兩家店的售價其實都是 \(990\)，用這個式子算出來卻不一樣：

  • 店 1：標價 \(1800\)、折扣 \(45\)，算出 990.0000000000001
  • 店 2：標價 \(3000\)、折扣 \(67\)，算出 989.9999999999999

這是本站用 setprecision(16) 多印幾位看到的值；直接 cout 的話兩個都印 990，看不出差別。可是比大小時店 2 比店 1 小，< 就換成店 2——兩家其實同價，應該選編號小的店 1。題目給的數字都是整數，就全程用整數算，這種誤差根本不會出現。

一欄一欄打擂台。每一欄先讓第 \(1\) 家店上台（語法書 4.8 的第一種初值：拿第一個當初值），第 \(2\)～\(m\) 家店輪流挑戰，售價比較低才換：用 < 不用 <=，同價時留在台上的就是先上台、編號比較小的店。每一欄的最低售價加起來就是總價，最多 \(50 \times 50000 = 2.5 \times 10^6\)，int 裝得下。

#include <bits/stdc++.h>
using namespace std;

const int MAX_M = 50;
const int MAX_N = 50;

int p[MAX_M + 1][MAX_N + 1];   // p[i][j]：第 i 家店第 j 項商品的標價（都從 1 用起）
int d[MAX_M + 1];              // d[i]：第 i 家店的折扣
int store[MAX_N + 1];          // store[j]：第 j 項商品到哪家店買

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> p[i][j];
    for (int i = 1; i <= m; i++)
        cin >> d[i];

    int total = 0;
    for (int j = 1; j <= n; j++) {                       // 一項商品＝表格的一欄
        int best = p[1][j] / 100 * (100 - d[1]);         // 第 1 家店先上台
        int who = 1;
        for (int i = 2; i <= m; i++) {                   // 第 2～m 家店輪流挑戰
            int sale = p[i][j] / 100 * (100 - d[i]);     // 標價是 100 的倍數：售價一定是整數
            if (sale < best) {                           // 比較便宜才換：同價時留下編號小的
                best = sale;
                who = i;
            }
        }
        store[j] = who;
        total += best;
    }
    for (int j = 1; j <= n; j++) {
        if (j > 1) cout << ' ';                          // 數字之間一個空白
        cout << store[j];
    }
    cout << '\n' << total << '\n';
    return 0;
}

兩個範例都有 \(-1\)，這份程式交上去兩個範例都會 WA——這是正常的，逐筆給分之下子題組 1 的 \(60\) 分穩穩到手；想自己驗，用自測表的第 1、2、5 列（都沒有 \(-1\)）。

從 60 分到 100 分：跳過沒賣的店、換掉擂台的初值

有店沒賣時，子題版有兩個地方會出事：

  • 沒賣的店變成免費：\(-1\) 照樣代進去，-1 / 100 是 \(0\)（整數除法向零取整，語法書 2.6），售價就是 \(0\) 元，比誰都便宜。所以先看標價，是 \(-1\) 就 continue，這家店不參加。
  • 第 1 家店不一定能先上台：它可能沒賣這項商品（範例 1、範例 2 的商品 3 都是）。改用語法書 4.8 的第二種初值：先放一個比所有售價都大的數。售價最多是 \(50000\)（標價 \(50000\)、折扣 \(0\)），初值設 \(50001\)，第一家有賣的店一定換得上去；who 先設 \(0\)，表示還沒有店上台。

初值不能剛好設 \(50000\)：某項商品最便宜如果就是 \(50000\)，50000 < 50000 不成立，沒有店上得了台，who 停在 \(0\)。

拿範例 1 的商品 3 走一次：店 1 沒賣，跳過；店 2 售價 \(140 < 50001\)，上台；店 3 售價 \(150\) 沒有比 \(140\) 小，不換。答案是店 2、\(140\) 元。

#include <bits/stdc++.h>
using namespace std;

const int MAX_M = 50;
const int MAX_N = 50;

int p[MAX_M + 1][MAX_N + 1];   // p[i][j]：第 i 家店第 j 項商品的標價（都從 1 用起）
int d[MAX_M + 1];              // d[i]：第 i 家店的折扣
int store[MAX_N + 1];          // store[j]：第 j 項商品到哪家店買

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> p[i][j];
    for (int i = 1; i <= m; i++)
        cin >> d[i];

    int total = 0;
    for (int j = 1; j <= n; j++) {                       // 一項商品＝表格的一欄
        int best = 50001;                                // 比任何售價都大：售價最多 50000
        int who = 0;                                     // 0：還沒有店上台
        for (int i = 1; i <= m; i++) {                   // 第 1 家店也要挑戰
            if (p[i][j] == -1) continue;                 // 這家店沒賣
            int sale = p[i][j] / 100 * (100 - d[i]);     // 標價是 100 的倍數：售價一定是整數
            if (sale < best) {                           // 比較便宜才換：同價時留下編號小的
                best = sale;
                who = i;
            }
        }
        store[j] = who;
        total += best;
    }
    for (int j = 1; j <= n; j++) {
        if (j > 1) cout << ' ';                          // 數字之間一個空白
        cout << store[j];
    }
    cout << '\n' << total << '\n';
    return 0;
}

表格最多 \(50 \times 50 = 2500\) 格，每一格只看一次，時間完全不是問題。

測過再交：範例的同價剛好算得準，也沒有 0 元和 50000 元

兩個範例已經考到沒賣的店（第 1 家店也有沒賣的商品）、同價選編號小的店；但範例 2 的同價用小數算也剛好相等，而且沒有 \(0\) 元、\(50000\) 元、折扣 \(100\) 的店。用小數算、初值設 \(50000\)、把 \(0\) 當記號、把沒賣當成很貴，這幾種寫法兩個範例都會過，下面幾列專門抓它們：

輸入 正確輸出 這一筆在測什麼
2 1 ／ 300 ／ 800 ／ 44 79 1 ／ 168 兩家店都是 \(168\) 元：用上面的小數算法，店 2 會比店 1 小一點點
3 1 ／ 0 ／ 40000 ／ 500 ／ 0 100 0 1 ／ 0 \(0\) 元：店 1 標價 \(0\)、店 2 折扣 \(100\)，兩家都免費，選店 1
2 1 ／ -1 ／ 50000 ／ 0 0 2 ／ 50000 最便宜剛好 \(50000\)（售價的最大值），而且只有店 2 有賣
2 1 ／ -1 ／ 500 ／ 100 0 2 ／ 500 沒賣的店 1 折扣是 \(100\)：它不能被當成 \(0\) 元
用程式造：\(m = n = 50\)，標價全是 \(50000\)、折扣全是 \(0\) \(50\) 個 1 ／ 2500000 總價最大；每項商品 \(50\) 家同價，都選店 1

五筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 照題目的式子寫成 p * ((100 - d) / 100)：括號裡先做整數除法，有打折的店售價都變成 \(0\)——範例 1 印 1 1 2 1／0。
  • 用小數算售價（p * (1 - d / 100.0)）：兩個範例都過，自測表第 1 列印 2；總價也用 double 加起來直接 cout，第 5 列還會印成 2.5e+06。
  • 同價用 <=：同價就換成後面的店——範例 2 印 2 2 2。
  • 只補了跳過 \(-1\)，初值還是拿第 1 家店：範例 1 印 2 1 1 3／430，商品 3 停在沒賣的店 1。
  • 沒賣當成「很貴」（標價改成 \(10^9\) 再打折）：兩個範例都過；折扣 \(100\) 的店不管標價多少都是 \(0\) 元，自測表第 4 列印 1／0。
  • 初值設成 \(50000\)：兩個範例都過，自測表第 3 列印 0。
  • 把 \(0\) 當成記號：用 best == 0 代表「還沒找到」，\(0\) 元的店會被下一家換掉，自測表第 2 列印 3／500；用 p <= 0 判斷沒賣，標價 \(0\) 的店被跳過，同一列印 2／0。