首页 > 代码库 > AC日记——Broken BST codeforces 797d
AC日记——Broken BST codeforces 797d
D - Broken BST
思路:
二叉搜索树;
它时间很优是因为每次都能把区间缩减为原来的一半;
所以,我们每次都缩减权值区间。
然后判断dis[now]是否在区间中;
代码:
#include <map>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define maxn 100005#define INF 0x7fffffffint n,ch[maxn][2],dis[maxn],ans;int l[maxn],r[maxn],root;bool if_[maxn];map<int,int>ma;map<int,bool>maa;inline void in(int &now){ int if_z=1;now=0; char Cget=getchar(); while(Cget>‘9‘||Cget<‘0‘) { if(Cget==‘-‘) if_z=-1; Cget=getchar(); } while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); } now*=if_z;}void dfs(int now,int l,int r){ if(l>r) return ; if(dis[now]>=l&&dis[now]<=r) { if(!maa[dis[now]]) { ans+=ma[dis[now]]; maa[dis[now]]=true; } } if(ch[now][0]!=-1) dfs(ch[now][0],l,min(dis[now]-1,r)); if(ch[now][1]!=-1) dfs(ch[now][1],max(l,dis[now]+1),r);}int main(){ in(n); for(int i=1;i<=n;i++) { in(dis[i]),in(ch[i][0]),in(ch[i][1]),ma[dis[i]]++; if(ch[i][0]!=-1) if_[ch[i][0]]=true; if(ch[i][1]!=-1) if_[ch[i][1]]=true; } for(int i=1;i<=n;i++) { if(!if_[i]) { root=i; break; } } dfs(root,0,INF); cout<<n-ans; return 0;}
AC日记——Broken BST codeforces 797d
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。