我要评论D. Minimal Height Tree
题目链接-D. Minimal Height Tree
题目大意
有一棵树，其子节点都是按照升序摆列，现在给出广度优先搜索的访问次序，请你求出该树的最小深度
解题思路
b
f
s
思
想
+
贪
心
bfs思想+贪心
bfs思想+贪心
- 刚开始开始我们易得
mp[0]=1，每次用mp[ans]++记录每一深度的可用的节点数目，对于一段严格单增的区间，必然是放在同一个父节点下面最好 - 从第二个节点开始遍历，当
a[i]<a[i-1]时，说明a[i]和a[i-1]不能连在同一父节点上，需要换另一个节点，若想深度最小，肯定优先考虑上一层可用节点，此时mp[ans-1]--即可 - 如果
mp[ans-1]==0，则说明上一层已无可连接的节点，需要另起一层，所以ans++记录层数 - 具体操作见代码
附上代码
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
inline void read(int &x){
char t=getchar();
while(!isdigit(t)) t=getchar();
for(x=t^48,t=getchar();isdigit(t);t=getchar()) x=x*10+(t^48);
}
int a[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n,ans=1;
cin>>n;
map<int,int> mp;
for(int i=1;i<=n;i++)
cin>>a[i];
mp[0]=1;
for(int i=2;i<=n;i++){
if(a[i]<a[i-1])
mp[ans-1]--;
if(mp[ans-1]==0)
ans++;
mp[ans]++;
}
cout<<ans<<endl;
}
return 0;
}
本文地址：https://blog.csdn.net/Fiveneves/article/details/109349368
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论