社区讨论

迷惑错误

SP1805HISTOGRA - Largest Rectangle in a Histogram参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lxlku8et
此快照首次捕获于
2024/06/19 16:34
2 年前
此快照最后确认于
2024/06/19 19:57
2 年前
查看原帖
一直在wa,但是不知道为什么,能找到的hack数据都过了
C
#include <bits/stdc++.h>
using namespace std;
int n;
int h[100010];
long long ans;

int main() {
    freopen(".in", "r", stdin);
    // cin.tie(0)->sync_with_stdio(0);
    stack<pair<int, int>> s;
    while (cin >> n, n) {
        ans = 0;
        for (int i = 1; i <= n; i++)
            cin >> h[i];
        h[n + 1] = 0;
        for (int i = 1; i <= n + 1; i++) {
            int width = 0;
            while (!s.empty() && h[s.top().first] > h[i]) {
                width += s.top().second;
                ans = max(ans, (long long)width * h[s.top().first]);
                s.pop();
            }
            s.push({ i, width + 1 });
        }
        s.pop();
        cout << ans << "\n";
    }
}

回复

4 条回复,欢迎继续交流。

正在加载回复...