#include <iostream>
#include <stack>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 100010;

int n;
long long h[maxn], sum[maxn];   // h[i]表示第i天的情感价值，sum[i]表示第1到i天的情感价值和
stack< pair<int,long long> > stk; // a.first 存放坐标； a.second 存放高度
long long ans;
int ans_l, ans_r;

void init() {
    ans = 0;
}


void test(int id) {
    printf("【test id = %d】\n" , id);
    stack< pair<int, long long> > tmp_stk;
    cout << "stk.size = " << stk.size() << endl;
    while (!stk.empty()) {
        pair<int, long long> pp = stk.top();
        stk.pop();
        tmp_stk.push(pp);
        cout << "\t" << pp.first << " , " << pp.second << endl;
    }
    while (!tmp_stk.empty()) {
        stk.push(tmp_stk.top());
        tmp_stk.pop();
    }
}


int main() {
    while (cin >> n) {
        init();
        for (int i = 1; i <= n; i ++) {
            cin >> h[i];
            sum[i] = sum[i-1] + h[i];
        }
        for (int i = 1; i <= n; i ++) {
            if (stk.empty() || stk.top().second < h[i])
                stk.push(make_pair(i, h[i]));
            else {
                int tmp_l = i;
                while (!stk.empty() && stk.top().second >= h[i]) {
                    pair<int, long long> pp = stk.top();
                    stk.pop();
                    tmp_l = pp.first;
                    long long tmp_h = pp.second;
                    long long tmp_ans = tmp_h * ( sum[i-1] - ( tmp_l == 1 ? 0 : sum[tmp_l-1] ) );
                    if (tmp_ans > ans) {
                        ans = tmp_ans;
                        ans_l = tmp_l;
                        ans_r = i - 1;
                        // cout << "check: " << tmp_ans << " : " << ans_l << " , " << ans_r << endl;
                        // cout << "check tmp_h = " << tmp_h << endl;
                    }
                }
                stk.push(make_pair(tmp_l, h[i]));
            }
            // test(i);
        }
        // 最后还要处理一下栈中存留下来的所有元素

        // test(0);

        while (!stk.empty()) {
            pair<int, long long> pp = stk.top();
            stk.pop();
            int tmp_l = pp.first;
            long long tmp_h = pp.second;
            long long tmp_ans = tmp_h * ( sum[n] - (tmp_l == 1 ? 0 : sum[tmp_l-1]) );
            if (tmp_ans > ans) {
                ans = tmp_ans;
                ans_l = tmp_l;
                ans_r = n;
            }
        }
        cout << ans << "\n" << ans_l << " " << ans_r << endl;
    }
    return 0;
}

• Re:搞不懂代码哪里有问题啊，求大神指教啊，万分感谢！ (124) zifeiy 2019-06-08 14:15:30