menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[LIS]洛谷3365【改造二叉树】题解
apps 洛谷
local_offer 查看标签
comment 0 条评论

题目概述

给出一棵 $n$ 个节点的二叉树,现在可以修改任意个节点的权值(只能改成整数),问至少多少次能把这棵二叉树改成BST。

解题报告

先中序遍历得到序列,然后就是用最少的次数把这个序列改成上升的。

但是只能改成整数,所以需要满足 $a_j-a_i\ge j-i$ ,转化成 $a_j-j\ge a_i-i$ 就行了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000;

int n,a[maxn+5],son[maxn+5][2],b[maxn+5],tem[maxn+5],c[maxn+5],ans;

inline int Find(int x) {int L=1,R=tem[0],mid;while (L<=R) tem[mid=L+(R-L>>1)]<=x?L=mid+1:R=mid-1;return R;}
void Dfs(int x) {if (!x) return;Dfs(son[x][0]);b[++b[0]]=a[x];Dfs(son[x][1]);}
inline void Update(int x,int now) {for (int i=x;i<=tem[0];i+=i&-i) c[i]=max(c[i],now);}
inline int Max(int x) {int MAX=0;for (int i=x;i;i-=i&-i) MAX=max(MAX,c[i]);return MAX;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=2,fa,d;i<=n;i++) scanf("%d%d",&fa,&d),son[fa][d]=i;
    Dfs(1);for (int i=1;i<=n;i++) tem[++tem[0]]=(b[i]-=i);
    sort(tem+1,tem+1+tem[0]);tem[0]=unique(tem+1,tem+1+tem[0])-tem-1;
    for (int i=1,now;i<=n;i++) b[i]=Find(b[i]),ans=max(ans,now=Max(b[i])+1),Update(b[i],now);
    return printf("%d\n",n-ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up