目录
1.题目
问题描述
约翰的N(1≤N≤10^5)头奶牛站成一排，奶牛i的身高是Hi(l≤Hi≤1,000,000)．现在，每只奶牛都在向右看齐．对于奶牛i，如果奶牛j满足i<j且Hi<Hj，我们可以说奶牛i可以仰望奶牛j．
求出每只奶牛离她最近的仰望对象．
输入格式
第1行输入N，之后每行输入一个身高．
输出格式
共N行，按顺序每行输出一只奶牛的最近仰望对象．如果没有仰望对象，输出0．
样例输入 1
6
3
2
6
1
1
2
样例输出 1
3
3
0
6
6
0
样例输入 2
10
1
13
13
14
7
9
3
9
3
15
样例输出 2
2
4
4
10
6
10
8
10
10
0
题目大意
其实可以把本体看成就求序列中每一个在其右边的第一个比它大的值，就是向右找寻第一个比他本身大的值，并且储存下来，没找到则得0。
2.分析
当我第一次看到这题的时候，第一个想到的就是用双重循环来做，我自信满满的写下了代码，嗯，然后我TLE了…………
TLE代码
#include<bits/stdc++.h>
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;
}暴力枚举见祖宗，十年OI一场空。
所以我们要用一些技巧
这道题原本灰常简单，只是需要考虑如何优化时间，那么就只有在处理数据的时候下功夫了，其实就有点像是递推的思维，就是要在比对的时候，采用一个跳跃的思维，就好比如有这样一组数据:3 2 6 1 1 2，那么选取其中的6，那么6就要和它右边的1进行比较，因为6>1，所以这个时候，就把1的仰望对象与6进行对比，这样就可以节省在2的仰望对象与2之间的这些数据的比较了，从而达到优化的效果。然后经过递推一点点推回来，我采用的是倒序的方法。
int j=0;
for(int i=n-1;i>=1;i--)
{
j=i+1;
while(a[i]>=a[j]&&a[j]>0)
{
j=ans[j];
}
ans[i]=j;
}3.AC代码
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int ans[100010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int j=0;
for(int i=n-1;i>=1;i--)
{
j=i+1;
while(a[i]>=a[j]&&a[j]>0)
{
j=ans[j];
}
ans[i]=j;
}
for(int i=1;i<=n;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}//完结撒花!
标签：10,int,仰望,NKOJ,样例,ans,奶牛,输入 From： https://blog.csdn.net/2402_83602026/article/details/142367809