（codeforce319）B.Psychos in a Line（单调栈）

题目链接：Problem - 319B - Codeforces

样例输入：

10
10 9 7 8 6 5 3 4 2 1

 样例输出：

2

简化题意：有n个人编号分别为1~n，每个人手里面有一把枪，瞄准右边相邻的人，如果自己的编号大于右边相邻的人的编号，就开枪打死自己右边相邻的人，所有人开枪的动作是同时发生的，一次开枪视作一轮，当且仅当每个人都不能开枪杀死自己右边相邻的人为止，问游戏最多经过多少轮结束。

分析：我们先来思考一个问题，就是第i个人什么时候死，首先可以确定的是如果第i个人死的话那么他一定是被他左边且编号比他大的人杀死的，当第i个人比他左边与他紧紧相邻的人的编号大时他一定比他左边的这个人死的晚，因为只有他左边编号比他小的人都死完，他左边才可能变成一个编号比他大的人，当他左边比他小的人都死了，那么下一个一定就轮到第i个人了，而且他是在比他小的人死亡后的下一轮次死亡的。所以我们可以用f[i]记录第i个人死亡的轮次，当且仅当第i个人不会死才会有f[i]=0，然后用单调栈模拟这个过程，所有被当前元素pop的元素都是在当前元素之前死亡的，而比自己编号小的元素都死亡后就轮到自己了，所以我们可以在pop过程中记录一个死亡的轮次最大值，而对应于死亡最大轮次的那个些编号就是隔在第i个数和杀死第i个人中间的最后一组连续的编号递减的数。那么当前元素就是在最大值的后一次死亡的，我们最后只需要在维护单调栈的过程中记录一下最大值即可，不要忘记把每个元素入栈。

下面是代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int N=1e5+10;
int a[N],f[N];
//a[i]记录第i个人的编号
//f[i]记录自己死亡的游戏轮次，未死亡标记为0
int st[N],tt; 
int main()
{
	int n;
    cin>>n;
    for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
    int ans=0;
    for(int i=1;i<=n;i++)
	{
        int t=0;
        while(tt&&a[st[tt]]<a[i])
            t=max(t,f[st[tt--]]);
        if(!tt) st[++tt]=i,f[i]=0;
        else st[++tt]=i,f[i]=t+1;
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}