CF 196B(Psychos in a Line-单调队列贪心)

B. Psychos in a Line
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who has an id greater than the psycho to his right (if exists) kills his right neighbor in the line. Note that a psycho might kill and get killed at the same step.

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 test(s)
input
10
10 9 7 8 6 5 3 4 2 1
output
2
input
6
1 2 3 4 5 6
output
0
Note
In the first sample line of the psychos transforms as follows: [10 9 7 8 6 5 3 4 2 1] → [10 8 4] → [10]. So, there are two steps.

考试的时候一直想这题是单调队列优化DP的LIS??结果试了半天没试出来。

......

听CCR说这题没错是单调队列，一个人杀人的次数可以NlogN求出来。。。=调换的次数（没听懂。。。）

讲一下辛苦YY的O(n)做法：

令f[i]表示[i,n]中i杀人的次数

从后向前推

若i杀得到j(不会被其它人杀) 则

（1）i把j杀时j未杀完,j未杀的归i

（2）j杀完，i杀j

可以用单调队列判断j是i第几个杀的

[cpp]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define MAXN (100000+10)
int n,st[MAXN],size=0,a[MAXN],kill[MAXN]={0},f[MAXN]={0};
int main()
{
    freopen("CF319B.in","r",stdin);
    int ans=0;
    scanf("%d",&n);
    For(i,n) cin>>a[i];
    ForD(i,n)
    {
        int t=0;
        while (size&&a[st[size]]<a[i]) {t++,f[i]=t=max(t,f[st[size]]),size--;}
        st[++size]=i;
        ans=max(ans,t);
    }
    cout<<ans<<endl;
    return 0;
}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define MAXN (100000+10)
int n,st[MAXN],size=0,a[MAXN],kill[MAXN]={0},f[MAXN]={0};
int main()
{
freopen("CF319B.in","r",stdin);
int ans=0;
scanf("%d",&n);
For(i,n) cin>>a[i];
ForD(i,n)
{
  int t=0;
  while (size&&a[st[size]]<a[i]) {t++,f[i]=t=max(t,f[st[size]]),size--;}
  st[++size]=i;
  ans=max(ans,t);
}
cout<<ans<<endl;
return 0;
}

补充：软件开发 , C++ ,