3213. 向右看齐

Deuchie

一看到奶牛,就知道这是 USACO 系列题啦,它们总是写点奶牛题233333

单调栈

本题的知识点叫「单调栈」。即使不知道这个东西也没问题,听我分析一下思路吧。

每头奶牛 $i$ 都只能向右看到比它还高的奶牛,所以它右面比它还低的奶牛相当于不存在(对小个子的恶意吗)。同时由于 $i$ 号奶牛比右面比它还低的奶牛高,所以这些矮奶牛再也没有被看到的机会了。换句话说,每头奶牛 $i$ 右侧所有可以看到的奶牛,必然是单调递增的。

#include "bits/stdc++.h"
using namespace std;

constexpr int INF = 0xFFFFFFF;
int h[1000001]{INF};

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
    stack<int> monostack; // Stores cows' id.
    monostack.push(0);
    vector<int> ans_rev;
    for (int i = n; i > 0; --i) {
        while (h[monostack.top()] <= h[i])
            monostack.pop();
        ans_rev.push_back(monostack.top());
        monostack.push(i);
    }
    for (auto i = ans_rev.rbegin(), ed = ans_rev.rend(); i != ed; ++i)
        cout << *i << '\n';
}
你当前正在回复 博客/题目
存在问题!