POJ练习题之:败方树

问题描述

给定一个整数数组,要求对数组中的元素构建败方树(数组相邻元素两两比较,从第一个元素开始)。之后修改数组中的元素,要求输出初始构建以及修改后得到的败方树的所有内部结点代表的整数(从左到右从上到下输出)

输入
第一行为数组的元素个数n和修改的次数m。
第二行为n个整数,即数组的元素。
接下来m行代表m次修改操作,每次操作修改数组中的一个元素,每一行包括两个整数,第一个为被修改元素在数组中的标号,第二个为修改之后的元素值。
输出
输出m+1行。
第一行为初始构建的败方树的所有内部结点代表的整数(按照树的结点从左到右从上到下的顺序输出)
接下来m行为接下来m次修改后得到的败方树的所有内部结点代表的整数(按照树的结点从左到右从上到下的顺序输出)
样例输入
8 1
10 9 20 6 16 12 90 17
3 15
样例输出
6 12 9 17 10 20 16 90
9 12 15 17 10 20 16 90

该题总体思路比较直观,就是模拟创建败者树的过程
总共就是初始建树和修改两个步骤
由于在败者树当中想要建立上一层的根节点需要知道赢者,而找到赢者需要回溯底层节点
观察到有的博客的建树思路是在每一次建立一个节点都向上一直更新到根节点(这样就不需要去做向下回溯寻找赢者的步骤了)
但是这样子建树第一遍是不完备的(受到顺序的影响),所以需要再做一遍
如下的代码思路比较直观,寻找赢者节点是直接使用的递归
POJ上的测试数据并不大,基本上不管使用什么思路只要是正确的应该不会存在超时或者爆栈 的问题。
整体代码由于是利用数组指针对败者树进行模拟,所以指针位置的操作比较繁琐,略显复杂,使部分代码不是很直观

#include<iostream>
using namespace std;
int A[1001];//将数组设为全局变量更有利于操作 
int n,m;//同理设为全局变量 
class Loser_tree{//创建败者树类,所有函数均在类中定义 
	public:
	int len;//败者树数组的长度 
	int Max_N;//树的最底层元素的个数 
	int floor;//败者树的层数(除去赢者节点Tree_Array[0]) 
	int *Tree_Array;//败者树数组指针 
	void Build(int );//初始建树函数 
	Loser_tree(int );//构造函数 
	int Vers(int pos);//寻找赢者(利用递归从当前根节点向下) 
	void ReBuild(int ,int );//修改败者树之后的重建 
};
Loser_tree::Loser_tree(int n){
	len=0;
	floor=0;
	Max_N=n/2;
	if(n%2)++Max_N;//根据奇偶确定败者树最底层元素个数 
	for(int s=Max_N;s>=1;s/=2) ++floor,len+=s;//确定层数和数组长度 
	Tree_Array=new int[len+1];//
	Build(n); //建树 
	
}
void Loser_tree::Build(int n){
	int father;
	int l=n%2 ? n-1:n;//
	for(int i=0,j=1;i<l;i+=2,++j){//先将最底层建立 
		father=len-Max_N+j;
		Tree_Array[father]=A[i]>A[i+1] ? i:i+1;
	}
	if(n%2) Tree_Array[len]=A[n-1];//若为奇数则树最后节点补充 
	int sum=len-Max_N;
	int a,b;
	for(int s=1,j=2;s<floor;++s,j*=2){//从最底层逐层向上 
		sum-=Max_N/j;
		for(father=sum+1;father<=sum+Max_N/j;++father){
			a=Vers(2*father);//
			b=Vers(2*father+1);//寻找赢者 
			Tree_Array[father]=A[a]>A[b] ? a:b;
		}
	}
	Tree_Array[0]=Vers(1);
}
int Loser_tree::Vers(int pos){
	if(pos>len-Max_N){//若到达最底层 
	if(Tree_Array[pos]==n-1&&Tree_Array[pos]%2==0) return n-1;
	else return Tree_Array[pos]%2 ? Tree_Array[pos]-1 :Tree_Array[pos]+1;
	}
	else {//若不在最底层则向下递归 
		int a,b;
		a=Vers(2*pos);
		b=Vers(2*pos+1);
		return A[a]<A[b]? a:b;
	}
}
void Loser_tree::ReBuild(int pos,int val){//重建 
	int a=pos%2 ? pos-1:pos;
	int b=pos%2 ? pos:pos+1;
	int father=len-Max_N+(pos+2)/2;
	Tree_Array[father]=A[a]>A[b] ? a:b;
	father/=2;
	while(father>=1){
		a=Vers(2*father);
		b=Vers(2*father+1);
		Tree_Array[father]=A[a]>A[b] ? a:b;
		father/=2;
	}
//	cout<<endl;
	Tree_Array[0]=Vers(1);
}
int main(){

	cin>>n>>m;
	for(int i=0;i<n;++i)cin>>A[i];
	Loser_tree Tree(n);
	int len=Tree.len;
//	for(int i=0;i<n;++i) cout<<Tree.Tree_Array[i]<<" ";
//	cout<<endl;
	for(int i=0;i<=len;++i) cout<<A[Tree.Tree_Array[i]]<<" ";
	int pos,val;
	for(int i=0;i<m;++i){
		cout<<endl;
		cin>>pos>>val;
		A[pos]=val;
//		for(int i=0;i<n;++i)cout<<A[i]<<" ";
//		cout<<endl;
		Tree.ReBuild(pos,val);
//		for(int i=0;i<=len;++i) cout<<Tree.Tree_Array[i]<<" ";
//		cout<<endl;
		for(int i=0;i<=len;++i) cout<<A[Tree.Tree_Array[i]]<<" ";
	}
}

热门文章

暂无图片
编程学习 ·

初见springBoot

如果本文对您有所帮助,可以点一下赞👍本文只是学习笔记,欢迎指错,转载标明出处环境:JDK 1.8Mysql 5.5maven 3.6.3idea 20191、SSM框架和SpringBoot区别因为当springboot 嵌入springmvc的时候很多人以为它就是另一种web框架了,这是一种误区。事实上它和原有的springmvc相…
暂无图片
编程学习 ·

一篇文章带你搞懂 SpringBoot 的配置文件

文章目录一、SpringBoot 配置文件类型1. SpringBoot配置文件类型和作用2. application.yml配置文件3. SpringBoot配置信息的查询二、配置文件与配置类的属性映射方式1. 使用注解@Value映射2. 使用注解@ConfigurationProperties映射 一、SpringBoot 配置文件类型 1. SpringBoot配…
暂无图片
编程学习 ·

电信云堤·抗D(电信云堤清洗高防服务器)提供超强T级DDoS处理能力

电信云堤”下辖四大产品: 电信云堤DDoS攻击防护(简称“电信云堤抗D”) 电信云堤域名安全防护(简称“电信云堤域名无忧”) 电信云堤反钓鱼网站处置(简称:“电信云堤反钓鱼”) 电信云堤网站安全专家(简称:“电信云堤网站安全专家)电信云堤抗D “电信云堤抗D”依托于中…
暂无图片
编程学习 ·

8080端口被占怎么办 ,解决方法

用后端springboot启动,8080端口 报错 8080 in use 打开 控制台 win+R 输入 cmd 进入后输入netstat -ano 肉眼能找到找就完事了如果找不到 输入netstat -aon|findstr “8080”找到最后一列的那个数字 “26252”, 就是PID 码 然后打开系统的 任务管理器 ,你要是任务管理器都不…
暂无图片
中恒嘉业 ·

关于主从复制的超详细解析(全)

目录前言1. 主从复制1.1 方式2. Mysql的主从复制2.1 一主一从2.1.1 window和linux通讯2.1.2 linux和linux的通讯2.2 双主双从3. Redis的主从复制3.1 哨兵模式3.2 java代码结合前言 主要介绍mysql的主从复制以及redis的主从复制 能由浅入深的明白原理以及如何操作 再者&#xf…
暂无图片
郑州普通话 ·

Windows下安装及配置VS Code (C/C++)

Windows下安装及配置VS Code By YC 安装VS Code 登录VS Code官方网站&#xff1a;https://code.visualstudio.com/download下载所需要的VS Code 注意Windows版本分为user和system两类。User版会将VSC安装在Windows的用户个人目录下&#xff08;也可以手动更改&#xff09;。S…
暂无图片
郑州普通话 ·

C++——深拷贝与浅拷贝

好久之前学的了&#xff0c;在CLion上试一下&#xff0c;发现为什么用的浅拷贝还是可以正常运行&#xff0c;于是转到了CB&#xff0c;发现还是可以正常运行&#xff0c;最后用了VS2022&#xff0c;就不行。 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #incl…
暂无图片
代理记账 ·

在web应用中发送和接收Jakarta消息

Running the websimplemessage Example To Package and Deploy websimplemessage Using Maven _1、Make sure that GlassFish Server has been started (see Starting and Stopping GlassFish Server). _2、In a terminal window, go to: tut-install/examples/jms/websimp…
暂无图片
cgfy ·

C++学习日记2——函数、封装、对象特性

一、函数 1.1 函数默认参数 1.1.1 简介 在C中&#xff0c;函数的形参列表中的形参是可以有默认值的 1.1.2 语法 返回值类型 函数名 (参数 默认值) {} 1.1.3 代码 #include <iostream> using namespace std;// 函数的默认参数 int func(int a, int b 20, int c 30…
暂无图片
coreui ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
coreui ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
未来博客 ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
未来博客 ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
建站日记 ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
建站日记 ·

NLP聊天机器人原理(seq2seq模型)

一、seq2seq模型 1.概念 seq2seq是一个Encoder-Decoder结构的网络&#xff0c;它的输入是一个序列&#xff0c;输出也是一个序列。Encoder中将一个可变长度的信号序列变为固定长度的向量表达&#xff0c;Decoder将这个固定长度的向量变成可变长度的目标的信号序列。这个结构最…
暂无图片
mfbz ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
mfbz ·

全渠道会员通-天猫会员通3: 会员运营内容准备

在天猫会员通技术对接开发过程中&#xff0c;为了通知存量会员的通知工作&#xff0c;发挥会员通的优势&#xff0c;品牌需要做好以下事宜&#xff1a; 会员体系暂停公告&#xff1a;因会员通技术升级期间&#xff0c;会员服务将被暂停&#xff0c;店铺tab中会员入口将被下线&…
暂无图片
珊珊日记 ·

C# 执行Javascript脚本

c#教程https://www.xin3721.com/eschool/CSharpxin3721/ 前一阵子使用C#编写SCXML状态机&#xff0c;需要解析EMCScript表达式&#xff0c;使用了Jint库&#xff08;https://github.com/sebastienros/jint/)&#xff0c;当时感觉与C#之间的数据转换不是很方便。这两天有时间又关…
暂无图片
珊珊日记 ·

第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛

A.大学期末现状 题目描述 作为一名大学生的你&#xff0c;现在又到了期末查成绩的时候&#xff0c;当你的成绩大于等于60时请输出“jige,haoye!”,否则输出"laoshi,caicai,laolao"。 输入描述: 一行&#xff0c;一个整数x代表你的成绩&#xff08;0<x<100&a…