ZeroJudge 解題筆記：f443. 商品擺設 Merchandise

作者：王一哲
日期：2025年3月11日



ZeroJudge 題目連結：f443. 商品擺設 Merchandise

解題想法

寫法1，先找到最左側隔板的位置 pre，設定最大值 imax 為 0、最小值 imin 為 1000，接著再繼續往右找，如果這格是商品就更新 imax、imin 及對應的位置 pmax、pmin；再次遇到隔板時，將 pmax、pmin 的商品對調，重置 imax、imin；重複以上的過程直到讀完貨架資料為止。

寫法2，先設定前一個隔板的位置 pre 為 -1，依序掃過每一格，如果在第 i 格遇到隔板而且 pre 不等於 -1，再用 index、max、min 及串列切片找區間最大值、最小值位置。效率會比寫法1差一點。

Python 程式碼

寫法1，使用時間約為 18 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # 商品數量
    val = list(map(int, input().split()))  # 商品銷售量
    key = list(map(int, input().split()))  # 商品編號
    i, pre = 0, -1  # 目前正在檢查的位置，前一個隔板的位置
    while val[i] != -1 and i < n: i += 1  # 繼續執行直到遇到第一個隔板或出界為止
    if i < n: pre = i  # 如果還沒有出界，pre 設定為 i
    imax, imin = 0, 1000  # 商品銷售量最大值、最小值
    pmax, pmin = 0, 0  # 商品銷售量最大值、最小值對應的編號
    i += 1  # i 加 1，接下來找下一格
    while i < n:  # 繼續執行直到出界為止
        if val[i] == -1:  # 如果是隔板
            if i - pre > 1:  # 如果這個隔板與前一個隔板距離超過一格
                val[pmax], val[pmin] = val[pmin], val[pmax]  # 交換商品銷售量
                key[pmax], key[pmin] = key[pmin], key[pmax]  # 交換商品編號
                imax, imin = 0, 1000  # 重置商品銷售量最大值、最小值
            pre = i  # pre 設定為 i
        else:  # 如果是商品
            if val[i] > imax:  # 如果是新的最大值
                imax, pmax = val[i], i  # 更新 imax, pmax
            if val[i] < imin:  # 如果是新的最小值
                imin, pmin = val[i], i  # 更新 imin, pmin
        i += 1  # i 加 1
    print(*key)  # 印出最後的商品編號

寫法2，使用時間約為 40 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # 商品數量
    val = list(map(int, input().split()))  # 商品銷售量
    key = list(map(int, input().split()))  # 商品編號
    pre = -1  # 前一個隔板的位置
    for i in range(n):  # 依序掃過 0 ~ n-1 格
        if val[i] == -1:  # 如果是隔板
            if pre == -1: pass  # 如果還沒有找到最左側的隔板，不做任何事
            elif i - pre > 1:  # 如果這個隔板與前一個隔板距離超過一格
                pmax = val[pre+1:i].index(max(val[pre+1:i])) + pre+1  # pre+1 ~ i-1 區間最大值位置
                pmin = val[pre+1:i].index(min(val[pre+1:i])) + pre+1  # pre+1 ~ i-1 區間最小值位置
                val[pmax], val[pmin] = val[pmin], val[pmax]  # 交換商品銷售量
                key[pmax], key[pmin] = key[pmin], key[pmax]  # 交換商品編號
            pre = i  # pre 設定為 i
    print(*key)  # 印出最後的商品編號

C++ 程式碼

寫法1，使用時間約為 2 ms，記憶體約為 344 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 商品數量
    while(cin >> n) {
        int val[n], key[n];  // 商品銷售量，商品編號
        for(int i=0; i<n; i++) cin >> val[i];
        for(int i=0; i<n; i++) cin >> key[i];
        int i = 0, pre = -1;  // 目前正在檢查的位置，前一個隔板的位置
        while(val[i] != -1 && i < n) i++;  // 繼續執行直到遇到第一個隔板或出界為止
        if (i < n) pre = i;  // 如果還沒有出界，pre 設定為 i
        int imax = 0, imin = 1000, pmax = 0, pmin = 0;  // 商品銷售量最大值、最小值及對應的編號
        i++;  // i 加 1，接下來找下一格
        while(i < n) {  // 繼續執行直到出界為止
            if (val[i] == -1) {  // 如果是隔板
                if (i - pre > 1) {  // 如果這個隔板與前一個隔板距離超過一格
                    int tmp = val[pmax]; val[pmax] = val[pmin]; val[pmin] = tmp;  // 交換商品銷售量
                    tmp = key[pmax]; key[pmax] = key[pmin]; key[pmin] = tmp;  // 交換商品媥號
                    imax = 0; imin = 1000;  // 重置商品銷售量最大值、最小值
                }
                pre = i;  // pre 設定為 i
            } else {  // 如果是商品
                if (val[i] > imax) {  // 如果是新的最大值
                    imax = val[i]; pmax = i;  // 更新 imax, pmax
                }
                if (val[i] < imin) {  // 如果是新的最小值
                    imin = val[i]; pmin = i;  // 更新 imin, pmin
                }
            }
            i++;  // i 加 1
        }
        for(int i=0; i<n; i++) cout << key[i] << " \n"[i == n-1];  // 印出最後的商品編號
    }
    return 0;
}

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 商品數量
    while(cin >> n) {
        vector<int> val (n), key (n);  // 商品銷售量，商品編號
        for(int i=0; i<n; i++) cin >> val[i];
        for(int i=0; i<n; i++) cin >> key[i];
        int pre = -1;  // 前一個隔板的位置
        for(int i=0; i<n; i++) {  // 依序掃過 0 ~ n-1 格
            if (val[i] == -1) {  // 如果是隔板
                if (pre == -1) {  // 如果還沒有找到最左側的隔板，不做任何事
                    ;
                } else if (i - pre > 1) {  // 如果這個隔板與前一個隔板距離超過一格
                    int pmax = max_element(val.begin()+pre+1, val.begin()+i) - val.begin();  // pre+1 ~ i-1 區間最大值位置
                    int pmin = min_element(val.begin()+pre+1, val.begin()+i) - val.begin();  // pre+1 ~ i-1 區間最小值位置
                    swap(val[pmax], val[pmin]);  // 交換商品銷售量
                    swap(key[pmax], key[pmin]);  // 交換商品編號
                }
                pre = i;  // pre 設定為 i
            }
        }
        for(int i=0; i<n; i++) cout << key[i] << " \n"[i == n-1];  // 印出最後的商品編號
    }
    return 0;
}