ZeroJudge 解題筆記：j538. 賣場設置 (Market)

作者：王一哲
日期：2025年4月18日



ZeroJudge 題目連結：j538. 賣場設置 (Market)

解題想法

我是用字典儲存商品位置及數量，寫起來比較簡單。

Python 程式碼

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

import sys
from collections import defaultdict

for s in sys.stdin:
    s = s.strip().lower()  # 商品種類，去掉結尾的 \n 再轉成小寫
    t = input().strip()  # 商品數量，去掉結尾的 \n
    pos = defaultdict(list)  # 各商品種類所在的位置
    val = defaultdict(int)  # 各商品種類的數量
    for i, (k, v) in enumerate(zip(s, t)):  # 將 s, t 綁在一起輸出
        pos[k].append(i)  # 商品 k 的位置新增 i
        val[k] += int(v)  # 商品 k 的數量加 v
    ans = [0]*len(s)  # 記錄答案用的串列
    for k, p in pos.items():  # 依序讀取 pos 的 key, value
        a = val[k]//len(p)  # 平均數量
        r = val[k]%len(p)  # 餘數
        for i, x in enumerate(p[::-1]):  # 從 p 尾端往回讀取位置
            if i < r: ans[x] = a+1  # 後面 r 個位置數量為 a+1
            else: ans[x] = a  # 其它位置數量為 a
    print(*ans, sep="")  # 將 ans 拆開、印出，不加分隔符號

C++ 程式碼

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

#include <iostream>
#include <string>
#include <cctype>
#include <vector>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;  // 商品種類
    while(cin >> s) {
        int n = (int)s.size();  // 共有 n 個位置
        string t; cin >> t;  // 商品數量
        map<char, vector<int>> pos;  // 各商品種類所在的位置
        map<char, int> val;  // 各商品種類的數量
        for(int i=0; i<n; i++) {  // 將 s, t 綁在一起輸出
            char k = tolower(s[i]);  // 商品 k
            pos[k].push_back(i);  // 商品 k 的位置新增 i
            val[k] += t[i]-'0';  // 商品 k 的數量加 t[i]-'0'
        }
        vector<int> ans (s.size(), 0);  // 記錄答案用的串列
        for(auto it : pos) {  // 依序讀取 pos 的 key, value
            char k = it.first;
            vector<int> p = it.second;
            int m = (int)p.size();  // p 的長度
            int a = val[k]/m;  // 平均數量
            int r = val[k]%m;  // 餘數
            for(int i=0; i<m; i++) {  // 從 p 尾端往回讀取位置
                if (i < r) ans[p[m-1-i]] = a+1;  // 後面 r 個位置數量為 a+1
                else ans[p[m-1-i]] = a;  // 其它位置數量為 a
            }
        }
        for(int i=0; i<n; i++) cout << ans[i];  // 印出 ans
        cout << "\n";
    }
    return 0;
}