(codeforce319) b.psychos in a line (monotone stack)

Topic link ：Problem - 319B - Codeforces

The sample input ：

10
10 9 7 8 6 5 3 4 2 1

  Sample output ：

2

Simplify the question ： Yes n Individual numbers are 1~n, There is a gun in every hand , Aim at the person next to you on the right , If your number is greater than the number of the adjacent person on the right , Just shoot the person next to you on your right , All people shoot at the same time , One shot counts as one round , If and only if everyone can't shoot the person next to him on his right , Ask how many rounds the game ends at most .

analysis ： Let's think about a question first , That is the first. i When does a person die , The first thing to be sure of is If the first i If a person dies, he must have been killed by someone on his left with a larger number , When the first i When a person has a larger number than the person on his left who is close to him, he must die later than the person on his left , because Only his left numbered people smaller than him are dead , Only on his left can he become a person with a larger number , When all the people smaller than him on his left died , Then it must be the turn of i Personal , And he died in the next round after the death of someone younger than him . So we can use f[i] Record No. i The cycle of personal death , If and only if i Only when a person doesn't die f[i]=0, Then use monotone stack to simulate this process , All current elements pop All elements of die before the current element , When the elements smaller than their own number die, it's their turn , So we can pop Record the maximum value of a death round during the process , And those numbers corresponding to largest round of the death are separated by i Number and kill number i The last group of consecutive numbers among individuals decreases . Then the current element will die after the maximum , Finally, we only need to record the maximum value in the process of maintaining the monotone stack , Don't forget to put every element on the stack .

Here is the code ：

#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] Record No. i Personal number 
//f[i] Record the game rounds of your death , Not dead marked as 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;
}