【題解】Zerojudge c364 - 我鄙視你

用到的陣列：h(紀錄身高)、prefix(紀錄前綴和)、dp(dp[i]代表第i個人比左邊(或右邊)高的人數)、ans(紀錄最後答案)

以範例測資舉例：

5

140 150 170 180 160

首先前從左邊往右邊更新

140因為是最左邊的人，所以左邊沒人，dp[0] = 0，ans[0] = 0

150左邊有人，而且身高比140高，所以將指標移到140左邊，但是已經超過陣列了，所以結束。dp[1] = 1，ans[1] = prefix[1 - 1] - prefix[-1](定義為0) = 140

170比左邊的150高，且150贏的人數為1(dp[1] = 1)，所以170不用和140比較就知道170比較高(150>140、170>140)，dp[2] = 2，ans[2] = prefix[2 - 1] - prefix[-1] = 290

180也是同上，dp[3] = 3，ans[3] = prefix[3 - 1] - prefix[-1] = 460

160因為左邊的人比他高，所以dp[4] = 0，ans[4] = 0

接下來換從右邊開始，方法跟左邊一樣

算完直接把ans印出來就好了

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")

using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

typedef int64_t ll;

const int mxN = 1e6 + 1;

int n;
ll num[mxN], l[mxN] = {}, r[mxN] = {};

int main() {
	fastio;
	cin >> n;
	for(int i = 0; i < n; ++i)
		cin >> num[i];
	vector<int> st;
	st.push_back(0);
	for(int i = 1; i < n; ++i) {
		while(!st.empty() && num[i] > num[st.back()]) {
			l[i] += l[st.back()] + num[st.back()];
			st.pop_back();
		}
		st.push_back(i);
	}
	st.clear();
	st.push_back(n - 1);
	for(int i = n - 2; ~i; --i) {
		while(!st.empty() && num[i] > num[st.back()]){
			r[i] += r[st.back()] + num[st.back()];
			st.pop_back();
		}
		st.push_back(i);
	}
	for(int i = 0; i < n; ++i)
		cout << l[i] + r[i] << "\n";
	
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge c364 - 我鄙視你