51Nod 1272 最大距离 (栈或贪心)

 1 #include <cstdio>
 2 #include <queue>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <stack>
 7 using namespace std;
 8 
 9 typedef long long ll;
10 struct node{int v, id;};
11 stack<node>q, sq;
12 
13 int main(){
14     int n;
15     scanf("%d", &n);
16     while(!sq.empty())  sq.pop();
17     int ans = 0;
18     for(int i = 0;i < n;i++){
19         int x;
20         scanf("%d", &x);
21         node a;
22         a.v = x; a.id = i;
23         if(sq.size() == 0 || sq.top().v > x){
24             sq.push(a);
25         }
26         else{
27             while(sq.top().v <= x){
28                 ans = max(ans, i - sq.top().id);
29                 q.push(sq.top());
30                 sq.pop();
31                 if(sq.empty())
32                     break;
33             }
34             while(!q.empty()){
35                 sq.push(q.top());
36                 q.pop();
37             }
38         }
39     }
40     printf("%d
", ans);
41     return 0;
42 }

后来提交一波的时候，最后一组数据超时，于是改用贪心，排序一遍过的：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 50000+5;
 7 struct node{
 8     int id,v;
 9 }a[maxn];
10 
11 bool cmp(node xx,node yy)
12 {
13     if (xx.v!=yy.v)
14     return xx.v<yy.v;
15     return xx.id<yy.id;
16 }
17 
18 int main()
19 {
20     int n;
21     scanf("%d",&n);
22     for (int i=0;i<n;i++)
23     {
24         scanf("%d", &a[i].v);
25         a[i].id=i;
26     }
27     sort(a,a+n,cmp);
28     int ans = 0,Min=a[0].id;
29     for (int i=1;i<n;i++)
30     {
31         if (a[i].id > Min)
32             ans = max(ans, a[i].id-Min);
33         else Min = a[i].id;
34     }
35     printf("%d
",ans);
36     return 0;
37 }