B. Psychos in a Line
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/problemset/problem/319/B
Description
You're given the initial arrangement of the psychos in the line. Calculate how many steps are needed to the moment of time such, that nobody kills his neighbor after that moment. Look notes to understand the statement more precise.
Input
The first line of input contains integer n denoting the number of psychos, (1 ≤ n ≤ 105). In the second line there will be a list of n space separated distinct integers each in range 1 to n, inclusive — ids of the psychos in the line from left to right.
Output
Print the number of steps, so that the line remains the same afterward..
Sample Input
10
10 9 7 8 6 5 3 4 2 1
Sample Output
2
HINT
题意
给你一堆数，每个数次都可以吃掉他右边连续减小的序列，问你多少轮之后，会变成上升序列
题解：
一开始想的暴力，用并查集/链表优化一下，结果不幸被t（其实也是情理之中……
T的数据是 100000 1 2 3 4 5…… 99999
正解是单调队列，维护一个单调下降的序列，就可以找到一直杀到哪儿的位置。
f[i]表示杀人的次数
代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
#define maxn 1000005
#define mod 10007
#define eps 1e-5
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//************************************************************************************** int a[maxn];
int f[maxn];
int t[maxn];
int main()
{
int n=read(),top=,ans=;
for(int i=;i<n;i++)
a[i]=read();
for(int i=n-;i>=;i--)
{
int tt=;
while(top&&a[t[top-]]<a[i])
f[i]=tt=max(tt+,f[t[--top]]);
t[top++]=i;
}
printf("%d",*max_element(f,f+n));
}