洛谷P2947 [USACO09MAR]向右看齐Look Up

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<stack>
 4 #include<cctype>
 5 using namespace std;
 6 struct cow{
 7     int id;
 8     int data;
 9     cow(int id=0,int data=0):id(id),data(data){
10     }
11 }ans[100005]; 
12 stack<cow> q;
13 int n,tmp,cnt;
14 inline bool cmp(const cow &a,const cow &b)
15 {
16     return a.id<b.id;
17 }
18 int main()
19 {
20     scanf("%d",&n);
21     for(int i=1;i<=n;i++)
22     {
23         scanf("%d",&tmp);
24         while(!q.empty()&&q.top().data<tmp)
25         {
26             ans[++cnt]=q.top();
27             ans[cnt].data=i;
28             q.pop();
29         }
30         q.push(cow(i,tmp)); 
31     }
32     while(!q.empty()) 
33     {
34         ans[++cnt]=q.top();
35         ans[cnt].data=0;
36         q.pop();
37     }
38     sort(ans+1,ans+1+n,cmp);
39     for(int i=1;i<=n;i++) printf("%d
",ans[i].data);
40     return 0;
41 }