uva 6692 Lucky Number
题目大意是说，定义一个数的lucky number是距离i最远的j且满足（a[i]<a[j] i<j）。
问对所有数最大的lucky number是什么。
不必线段树。
我们可以先处理出a[i]的最远点。倒着扫一遍即可。
然后可以处理出大于等于a[i]的最远位置。
/*************************************************************************
> File Name: code/hust/20151115/A.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年11月23日 星期一 22时13分15秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#include<cctype>
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19using namespace std;
20const double eps = 1E-8;
21const int dx4[4]={1,0,0,-1};
22const int dy4[4]={0,-1,1,0};
23const int N=1E5+6;
24typedef long long LL;
25int a[N];
26int n;
27int p[N];
28const int inf = 0x3f3f3f3f;
29int main()
30{
31 #ifndef ONLINE_JUDGE
32 freopen("in.txt","r",stdin);
33 #endif
1 int T;
2 scanf("%d",&T);
3 while (T--)
4 {
5 scanf("%d",&n);
6 int mx = -1;
7 for ( int i = 1 ; i <= n ; i++ ) scanf("%d",&a[i]),mx = max(mx,a[i]);
1 ms(p,-1);
2 for ( int i = 1 ; i <= n ; i++)
3 p[a[i]] = max(p[a[i]],i); //最远的a[i]的位置
4 for ( int i = mx ; i >= 1 ; i--)
5 p[i] = max(p[i],p[i+1]);//cout<<"p[i]:"<<p[i]<<endl; //最远的>= a[i]的位置
1 int ans = 0;
2 for ( int i = 1 ; i <= n ; i++)
3 ans = max(ans,p[a[i]+1]-i);
4 printf("%d\n",ans);
}
1 #ifndef ONLINE_JUDGE
2 #endif
3 fclose(stdin);
4 return 0;
5}