题目链接
思路+历程
首先拿到题，我的第一思路是简单的模拟:先将奶牛从尾到头扫一遍，maxx[i]表示从最后一个到i的最高的奶牛，ip[i]表示那个奶牛的位置，这样一来就像前缀数组了如果h[i]<maxx[i]就令它的ans[i]=ip[i]，否则就更新maxx[i],使ans[i]=0;
自信满满地交了上去，WA了
20分WA代码
#include <bits/stdc++.h>
using namespace std;
int n;
int h[100005],maxx[100005],ip[100005],ans[100005];
int main() {
cin>>n;
for(int i=1;i<=n;i++)cin>>h[i];
for(int i=n;i>=1;i--){
maxx[i]=maxx[i+1];
ip[i]=ip[i+1];
if(h[i]<maxx[i]){
ans[i]=ip[i];
}else{
maxx[i]=h[i];
ip[i]=i;
ans[i]=0;
}
}
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
return 0;
}
后来我发现：这种思路是有缺陷的，题目要求的是往右看第一个高的奶牛，而我的做法会使第一个高奶牛被忽略，从而变成最高的奶牛。
在厕所里一阵思索后，我想出了另一种做法：以栈来存储奶牛中，对于当前奶牛，一直出栈直到遇到比它高的为止（相当于奶牛一眼望过去把矮的都给忽略了），然后将当前奶牛压入栈中，（它把矮的奶牛都挡住了），经过检验后，发现没有问题。
交上去，49分RE。
49分RE代码
#include <bits/stdc++.h>
using namespace std;
int n;
struct cow{
int hi;
int ip;
}a[100005];
cow st[100005];
int ans[10005];
int top=0;
int main() {
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].hi,a[i].ip=i;
st[0].ip=0,st[1].hi=0;
for(int i=n;i>=1;i--){
while(a[i].hi>=st[top].hi&&top>=1)top--;
ans[i]=st[top].ip;
st[++top].hi=a[i].hi;
st[top].ip=i;
}
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
return 0;
}
遇到这种情况，首先要判断三个问题：数组是否越界，数组规模是否太小，有没有开long long。
果不其然，数组ans开小了，少打了个0，修改后成功AC。
#include <bits/stdc++.h>
using namespace std;
int n;
struct cow{
int hi;
int ip;
}a[100005];
cow st[100005];
int ans[100005];
int top=0;
int main() {
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].hi,a[i].ip=i;
st[0].ip=0,st[1].hi=0;
for(int i=n;i>=1;i--){
while(a[i].hi>=st[top].hi&&top>=1)top--;
ans[i]=st[top].ip;
st[++top].hi=a[i].hi;
st[top].ip=i;
}
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
return 0;
}
大功告成！