洛谷 P2947 [USACO09MAR]仰望Look Up

谁践踏了优雅 2021-09-29 11:28 315阅读 0赞

## 题目描述 ##

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≤Hi≤1,000,000)．现在，每只奶牛都在向左看齐．对于奶牛i，如果奶牛j满足i<j且Hi<Hj，我们可以说奶牛i可以仰望奶牛j． 求出每只奶牛离她最近的仰望对象．

Input

## 输入输出格式 ##

输入格式：

*  Line 1: A single integer: N
 *  Lines 2..N+1: Line i+1 contains the single integer: 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.

## 输入输出样例 ##

输入样例\#1：

6 
    3 
    2 
    6 
    1 
    1 
    2

输出样例\#1：

3 
    3 
    0 
    6 
    6 
    0

## 说明 ##

FJ has six cows of heights 3, 2, 6, 1, 1, and 2.

Cows 1 and 2 both look up to cow 3; cows 4 and 5 both look up to cow 6; and cows 3 and 6 do not look up to any cow.

栈。

[屠龙宝刀点击就送][Link 1]

#include <cstdio>
    #define N 100005
    int a[N],num[N],ans[N],n,last,stack[N],top;
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);num[i]=i;
            if(!top) {stack[++top]=i;continue;}
            else if(a[stack[top]]<a[i])
            {
                for(;(a[stack[top]]<a[i])&&top;top--)
                ans[num[stack[top]]]=i;
            }
            stack[++top]=i;
        }
        for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/ruojisun/p/7388566.html

[Link 1]: https://www.luogu.org/problem/show?pid=2947