ZeroJudge 解題筆記：o344.超市掃貨

作者：王一哲
日期：2026年10月3日


ZeroJudge 題目連結：o344.超市掃貨

解題想法

這題雖然被放在基礎題庫，但其實根本不是基礎題。題目給一個正整數 $t$，代表接下來有 $t$ 組測資。每組測資為 2 行，第一行是一個正整數 $n$，代表共有 $n$ 個酪梨；第二行有 $n$ 個正整數，代表 $n$ 個酪梨的大小。取一段連續的區間，分數為區間和乘以區間最小值，找出所有可能的區間中的最高分。

由於這題要取區間和，而且區間的資料不變，很直覺會想要用前綴和計算區間和。假設重量記錄於陣列 $nums$ 之中，為了結算最後一項的分數，$nums$ 長度為 $n+1$，最後一項為 $0$。前綴和陣列 $psum$ 長度則為 $n+2$，索引值向右平移一格。這題困難之處在於取區間最小值，比較快速的寫法是利用單調隊列，用一個堆疊 $st$ 記錄目前讀到的最小值於重量陣列之中的索引值。用一個 for 迴圈跑 $i = 0$ 到 $i = n-1$，裡面再用一個 while 檢查 $nums[i]$ 是否大於等於 $nums[st[-1]]$，如果條件成立，代表從 $i$ 開始對應到新的最小值，要先結算 $st[-1]$ 到 $i$ 之間的區間，區間不包含左、右端點。步驟為：

1. 區間最小值 $imin = nums[st.pop()]$
2. 移除 $st[-1]$ 之後，此時區間左端點 $left = st[-1]$，如果 $st$ 是空的則設定為 $-1$。區間右端點 $right = i$。
3. 區間和 $isum = psum[right] - psum[left + 1]$，這是因為 $psum$ 索引值向右平移一格，因此 $psum[(right - 1) + 1] = psum[right]$；要減去的是 $nums[left + 1]$ 的前一項$，因此 $psum[(left + 1) + 1 - 1] = psum[left + 1]$。
4. 更新答案 $ans = max(ans, imin * isum)$

由於答案很大，如果用 C++ 解題要用 long long，否則會溢位。

Python 程式碼

解題時間約為 0.9 s，使用記憶體約為 134.4 MB。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    t = int(data[0])
    ptr = 1
    for _ in range(t):
        n = int(data[ptr])
        ptr += 1
        # 讀取酪梨大小，最後加 0 結算測資中最後一個酪梨
        nums = list(map(int, data[ptr : ptr + n])) + [0]
        ptr += n
        
        # --- 建立前綴和陣列 ---
        psum = [0] + nums[:]
        for i in range(n+1):
            psum[i+1] += psum[i]
        
        # --- 由左向右掃，堆疊 st 為酪梨大小嚴格遞增的索引值
        ans = 0  # 答案
        st = []
        for i in range(n + 1):
            # nums[i] 是新的最小值，結算 (st[-1] ~ (i-1) 區間的值
            while st and nums[i] <= nums[st[-1]]:
                imin = nums[st.pop()]  # 區間最小值
                left = st[-1] if st else -1  # 如果 st 有值，左邊界為 st 最後一項；反之為 -1
                right = i  # 右邊界為 i
                # 用前綴和陣列取區間和，psum 陣列的索引值向右平移 1 格
                isum = psum[right] - psum[left + 1]
                ans = max(ans, imin * isum)
            # 更新完區間答案，i 加入 st
            st.append(i)
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

解題時間約為 92 ms，使用記憶體約為 12.6 MB。

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        // 讀取酪梨大小，最後加 0 結算測資中最後一個酪梨，同時建立前綴和陣列
        vector<LL> nums (n+1, 0), psum (n+2, 0);
        for(int i = 0; i < n; i++) {
            cin >> nums[i];
            psum[i+1] = psum[i] + nums[i];
        }
        
        // --- 由左向右掃，堆疊 st 為酪梨大小嚴格遞增的索引值
        LL ans = 0;
        stack<int> st;
        for(int i = 0; i <= n; i++) {
            // nums[i] 是新的最小值，結算 st[-1] ~ (i-1) 區間的值
            while(!st.empty() && nums[i] <= nums[st.top()]) {
                LL imin = nums[st.top()];  // 區間最小值
                st.pop();
                int left = (!st.empty() ? st.top() : -1);  // 如果 st 有值，左邊界為 st 最後一項；反之為 -1
                int right = i;  // 右邊界為 i
                LL isum = psum[right] - psum[left + 1];  // 用前綴和陣列取區間和，psum 陣列的索引值向右平移 1 格
                ans = max(ans, imin * isum);
            }
            st.push(i);  // 更新完區間答案，i 加入 st
        }
        cout << ans << "\n";
    }
    return 0;
}

解題時間約為 0.1 s，使用記憶體約為 12.8 MB。

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
typedef long long LL;
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        // 讀取酪梨大小，最後加 0 結算測資中最後一個酪梨，同時建立前綴和陣列
        vector<LL> nums (n+1, 0), psum (n+2, 0);
        for(int i = 0; i < n; i++) {
            scanf("%lld", &nums[i]);
            psum[i+1] = psum[i] + nums[i];
        }
        
        // --- 由左向右掃，堆疊 st 為酪梨大小嚴格遞增的索引值
        LL ans = 0;
        stack<int> st;
        for(int i = 0; i <= n; i++) {
            // nums[i] 是新的最小值，結算 st[-1] ~ (i-1) 區間的值
            while(!st.empty() && nums[i] <= nums[st.top()]) {
                LL imin = nums[st.top()];  // 區間最小值
                st.pop();
                int left = (!st.empty() ? st.top() : -1);  // 如果 st 有值，左邊界為 st 最後一項；反之為 -1
                int right = i;  // 右邊界為 i
                LL isum = psum[right] - psum[left + 1];  // 用前綴和陣列取區間和，psum 陣列的索引值向右平移 1 格
                ans = max(ans, imin * isum);
            }
            st.push(i);  // 更新完區間答案，i 加入 st
        }
        printf("%lld\n", ans);
    }
    return 0;
}