自动搬运

查看原文

来自洛谷，原作者为

	胡萝卜2333333333 **

搬运于2025-08-24 21:43:43，当前版本为作者最后更新于2018-03-20 18:37:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

破题：

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

思路：

当我第一次看到这题的时候，第一个想到的就是用双重循环来做，但是我看了一眼题目的难度系数【普及/提高-】，所以这道题肯定有什么坑！但是我还是自信满满的写下了代码，嗯，然后我TLE了，GG。

双重循环代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
int n,i,j;
int a[100010];
int ans[100010];
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            if(a[i]<a[j])
            {
                ans[i]=j;
                break;
            }
        }
    }
    for(i=1;i<=n;i++)cout<<ans[i]<<endl;
    return 0;
}

很简单的代码，TLE了5个点。 【所以千万不要作死！！】

其实这道题考虑的只是如何将优化时间，那么就只有在处理数据的时候下功夫了，其实就有点像是递推的思维，就是要在比对的时候，采用一个跳跃的思维，就好比如有这样一组数据: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，否则就会陷入死循环而导致没有输出！！！