P2947 [USACO09MAR]Look Up S 详细题解

题目传送门

题目描述

Farmer John’s N (1 <= N <= 100,000) cows, conveniently numbered 1…N, are once again standing in a row. Cow i has height $H_i(1<=H_i$ <= 1,000,000).

Each cow is looking to her left toward those with higher index numbers. We say that cow i ‘looks up’ to cow j if i < j and $H_i<H_j$. For each cow i, FJ would like to know the index of the first cow in line looked up to by cow i.

Note: about 50% of the test data will have N <= 1,000.

约翰的N(1≤N≤$10^5$)头奶牛站成一排，奶牛i的身高是Hi$(l\le H_i\le 1,000,000)$．现在，每只奶牛都在向右看齐．对于奶牛i，如果奶牛j满足i<j且$H_i<H_j$，我们可以说奶牛i可以仰望奶牛j． 求出每只奶牛离她最近的仰望对象．

输入格式

* Line 1: A single integer: N

* Lines 2…N+1: Line i+1 contains the single integer: $H_i$

第 1 行输入 N，之后每行输入一个身高 $H_i$。

输出格式

* Lines 1…N: Line i contains a single integer representing the smallest index of a cow up to which cow i looks. If no such cow exists, print 0.

共 N 行，按顺序每行输出一只奶牛的最近仰望对象，如果没有仰望对象，输出 0。

解题思路：

这是一道单调栈模板题。由于是向右看齐，所以我们要先拿个数组存下所有奶牛的身高，然后倒序进行单调栈的操作。
$$\{\begin{array}{l}1.记录下所有奶牛的身高\\ 2.逆序进行单调栈操作：\{\begin{array}{l}1.栈非空弹出所有比当前奶牛矮的奶牛\\ 2.栈空？\{\begin{array}{l}1.空，没有可仰望的奶牛\\ 2.非空，栈顶即仰望的奶牛\end{array}\\ 3.将当前奶牛压入栈中\end{array}\end{array}$$
附上代码：

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

#define ll long long
#define INF 0x3f3f3f3f

const int maxn = 100005;
stack<int> s;
int arr[maxn],ans[maxn];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)  cin >> arr[i];//记录每头牛的高度
    for(int i = n;i >= 1;i--){//倒序开始单调栈操作
        while(s.size() && arr[s.top()] <= arr[i]) s.pop();//弹出所有不高于当前奶牛高度的奶牛
        ans[i] = (s.size() ? s.top() : 0);//奶牛仰望的就是栈顶奶牛，如果栈空则没有
        s.push(i);//把当前奶牛压入栈中
    }
    //输出结果
    for(int i = 1;i <= n;i++) cout << ans[i] << endl;

    return 0;
}

最后

以上就是想人陪冬天为你收集整理的P2947 [USACO09MAR]Look Up S 详细题解P2947 [USACO09MAR]Look Up S 详细题解的全部内容，希望文章能够帮你解决P2947 [USACO09MAR]Look Up S 详细题解P2947 [USACO09MAR]Look Up S 详细题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。