codeforces 1437D

题目链接：https://codeforces.com/problemset/problem/1437/D

模拟一遍 bfs，因为儿子是单增的，所以每一段单增的连续子序列肯定是贪心地在一个儿子里的，
这样就能保证高度最小了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int maxn = 200010;

int T,n,ans;
int a[maxn], pos[maxn], cnt, cur, now;

int head = 1,tail = 0;
int q[maxn];

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	T = read();
	while(T--){
		memset(pos,0,sizeof(pos));
		memset(q,0,sizeof(q));
		n = read(); cnt = 0; cur = 2; now = 1; ans = 0;
		
		for(int i=1;i<=n;++i) a[i] = read();
		
		head = 1; tail = 0;
		
		for(int i=1;i<=n;++i) if(a[i] < a[i-1]) pos[++cnt] = i - 1;
		pos[++cnt] = n;
		
		q[++tail] = 0;
		
		while(head <= tail){
//			printf("q: %d %d %d %d
",head,tail,q[head],q[tail]);
			int dep = q[head++] + 1; ans = max(ans, dep);
			for(cur;cur<=pos[now] && now <= cnt;++cur){
				q[++tail] = dep;	
			}
			if(now == cnt) break;
			++now;
		}
		
		printf("%d
",ans);
	}
	return 0;
}