ZeroJudge 解題筆記：c364. 我鄙視你

作者：王一哲
日期：2025年8月14日


ZeroJudge 題目連結：c364. 我鄙視你

解題想法

從每個人開始，向左、向右各找一次遞減序列。

Python 程式碼

從第9筆測資開始超過記憶體上限。

n = int(input())  # 人數
hs = [1000000001] + list(map(int, input().split())) + [1000000001]  # 身高，兩端加上很大的值
pre = [0]*(n+2)  # 前綴和
st = [0]  # 左側較高的人編號，先放入0
ans = [0]*(n+2)  # 每個人對應的答案，先預設為0
for i in range(1, n+1):  # 依序掃過第 1 ~ n 個人
    pre[i] = pre[i-1] + hs[i]  # 計算前綴和
    while hs[i] > hs[st[-1]]: st.pop()  # 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
    ans[i] = pre[i-1] - pre[st[-1]]  # 更新答案為第 i-1 ~ st[-1]+1 個人的身高總合
    st.append(i)  # 放入 i

post = [0]*(n+2)  # 後綴和
st = [n+1]  # 右側較高的人編號，先放入n+1
for i in range(n, 0, -1):  # 依序掃過第 n ~ 1 個人
    post[i] = post[i+1] + hs[i]  # 計算後綴和
    while hs[i] > hs[st[-1]]: st.pop()  # 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
    ans[i] += post[i+1] - post[st[-1]]  # 更新答案為第 i+1 ~ st[-1]+1 個人的身高總合
    st.append(i)  # 放入 i

for i in range(1, n+1): print(ans[i])  # 印出答案

C++ 程式碼

用 int 會溢位，改用 long long 不會溢位，但是從第9筆測資開始遇到記憶體區段錯誤。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    LL n; cin >> n;  // 人數
    LL hs[n+2]; hs[0] = 1e9+1; hs[n+1] = 1e9+1;  // 身高，兩端加上很大的值
    LL pre[n+2] = {0}, ans[n+2] = {0};  // 前綴和 pre；每個人對應的答案 ans，先預設為0
    stack<LL> st; st.push(0);  // 左側較高的人編號，先放入0
    for(LL i=1; i<=n; i++) {  // 依序讀取並掃過第 1 ~ n 個人
        cin >> hs[i];  // 讀取第 i 個人的身高
        pre[i] = pre[i-1] + hs[i];  // 計算前綴和
        while(hs[i] > hs[st.top()]) st.pop();  // 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
        ans[i] = pre[i-1] - pre[st.top()];  // 更新答案為第 i-1 ~ st.top()+1 個人的身高總合
        st.push(i);  // 放入 i
    }
    //LL post[n+2] = {0};  // 後綴和
    st = stack<LL> (); st.push(n+1);  // 清空 st，改成儲存右側較高的人編號，先放入n+1
    for(LL i=n; i>=1; i--) {  // 依序掃過第 n ~ 1 個人
        //post[i] = post[i+1] + hs[i];  // 計算後綴和
        while(hs[i] > hs[st.top()]) st.pop();  // 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
        ans[i] += pre[st.top()-1] - pre[i];  // 更新答案為第 i+1 ~ st[-2] 個人的身高總合
        st.push(i);  // 放入 i
    }
    for(LL i=1; i<=n; i++) cout << ans[i] << "\n";  // 印出答案
    return 0;
}

換一種宣告陣列的方式，使用時間約為 0.5 s，記憶體約為 31.3 MB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    LL n; cin >> n;  // 人數
    LL *hs = new LL[n+2]; hs[0] = 1e9+1; hs[n+1] = 1e9+1;  // 身高，兩端加上很大的值
    LL *pre = new LL[n+2]; LL *ans = new LL[n+2];  // 前綴和 pre；每個人對應的答案 ans，先預設為0
    memset(pre, 0, sizeof(pre)); memset(ans, 0, sizeof(ans));
    stack<LL> st; st.push(0);  // 左側較高的人編號，先放入0
    for(LL i=1; i<=n; i++) {  // 依序讀取並掃過第 1 ~ n 個人
        cin >> hs[i];  // 讀取第 i 個人的身高
        pre[i] = pre[i-1] + hs[i];  // 計算前綴和
        while(hs[i] > hs[st.top()]) st.pop();  // 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
        ans[i] = pre[i-1] - pre[st.top()];  // 更新答案為第 i-1 ~ st.top()+1 個人的身高總合
        st.push(i);  // 放入 i
    }
    st = stack<LL> (); st.push(n+1);  // 清空 st，改成儲存右側較高的人編號，先放入n+1
    for(LL i=n; i>=1; i--) {  // 依序掃過第 n ~ 1 個人
        while(hs[i] > hs[st.top()]) st.pop();  // 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
        ans[i] += pre[st.top()-1] - pre[i];  // 更新答案為第 i+1 ~ st[-2] 個人的身高總合
        st.push(i);  // 放入 i
    }
    for(LL i=1; i<=n; i++) cout << ans[i] << "\n";  // 印出答案
    return 0;
}

改用 vector 也可以，使用時間約為 0.5 s，記憶體約為 31.4 MB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    LL n; cin >> n;  // 人數
    vector<LL> hs (n+2, 0); hs[0] = 1e9+1; hs[n+1] = 1e9+1;  // 身高，兩端加上很大的值
    vector<LL> pre (n+2, 0), ans (n+2, 0);  // 前綴和 pre；每個人對應的答案 ans，先預設為0
    stack<LL> st; st.push(0);  // 左側較高的人編號，先放入0
    for(LL i=1; i<=n; i++) {  // 依序讀取並掃過第 1 ~ n 個人
        cin >> hs[i];  // 讀取第 i 個人的身高
        pre[i] = pre[i-1] + hs[i];  // 計算前綴和
        while(hs[i] > hs[st.top()]) st.pop();  // 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
        ans[i] = pre[i-1] - pre[st.top()];  // 更新答案為第 i-1 ~ st.top()+1 個人的身高總合
        st.push(i);  // 放入 i
    }
    st = stack<LL> (); st.push(n+1);  // 清空 st，改成儲存右側較高的人編號，先放入n+1
    for(LL i=n; i>=1; i--) {  // 依序掃過第 n ~ 1 個人
        while(hs[i] > hs[st.top()]) st.pop();  // 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
        ans[i] += pre[st.top()-1] - pre[i];  // 更新答案為第 i+1 ~ st[-2] 個人的身高總合
        st.push(i);  // 放入 i
    }
    for(LL i=1; i<=n; i++) cout << ans[i] << "\n";  // 印出答案
    return 0;
}