题目描述

Farmer John's N (1 <= N <= 100,000) cows, conveniently numbered 1..N, are once again standing in a row. Cow i has height Hi (1 <= Hi <= 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 Hi < Hj. 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.

输入描述:

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains the single integer: Hi

输出描述:

* 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
输出
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.

解答

破题：

其实可以把本体看成就求序列中每一个在其右边的第一个比它大的值，就是向右找寻第一个比他本身大的值，并且储存下来，没找到则得0。

其实这道题考虑的只是如何将优化时间，那么就只有在处理数据的时候下功夫了，其实就有点像是递推的思维，就是要在比对的时候，采用一个跳跃的思维，就好比如有这样一组数据:3 2 6 1 1 2，那么选取其中的6，那么6就要和它右边的1进行比较，因为6>1，所以这个时候，就把1的仰望对象与6进行对比，这样就可以节省在2的仰望对象与2之间的这些数据的比较了，从而达到优化的效果。然后经过递推一点点推回来，我采用的是倒序的方法。

下面是我的AC代码： 

#include<iostream>
#include<cstdio>
using namespace std;
int n,i,j,gg=1;
int a[100010];
int ans[100010];//定义
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];//输入
    for(i=n-1;i>=1;i--)//采用倒序，因为ans[n]=0，所以就从n-1开始
    {
        j=i+1;//先和它右边的第一个数进行比对
        while(a[i]>=a[j] && a[j]>0)j=ans[j];//如果没有找到比它自己大的数的话，就把另一个数的仰望对象与它进行比对
        ans[i]=j;//标记
    }

    for(i=1;i<=n;i++)cout<<ans[i]<<endl;//输出
    return 0;//over~~~~
}
！！！也是很简单的几行代码，但是要注意的是在if语句里的判断条件a[j]>0，因为在往回寻找仰望对象的同时，也会有涉及到ans[0]的时候，所以这时候要么使a[0]等于一个很大的数，要不就是在if语句之中添加一个a[j]>0，否则就会陷入死循环而导致没有输出！！！


来源：胡萝卜23333…