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]]<<" ";
	}
}

热门文章

暂无图片
编程学习 ·

javascript 实现所有浏览器异步加载的工具

javascript 实现所有浏览器异步加载的工具 //异步加载 实现 function loadScript(url, callback){ //新建一个script 元素 var script = document.createElement(‘script’); //再往script中添加类型 script.type=“text/javascript”; if(script.readyState){ //每当 rea…
暂无图片
编程学习 ·

Django入门笔记:第十三章、用户登录

前言 从之前的学习我们发现,一直在blog应用中进行开发。本章开始新建另一个App来开发,介绍Django的身份认证模块,实现用户登录、注册、注销。 一个简单的登录界面 创建应用 为了实现用户登录、退出、注册等功能,从而进行用户管理,创建一个新的应用。 python manage.py sta…
暂无图片
编程学习 ·

easyui datagrid deleteRow(删除行)的BUG

有时候想临时保存一些数据,等确定好后在批量一次提交,但EasyUI datagrid 用的时候添加可以正常,如果从中间删除那行号就全乱了。导致删除的时候有可能删除上一行数据。function addFileRow(){$(#FileTable).datagrid(appendRow,{ File_Name:"aaaa",File_Path:&qu…
暂无图片
编程学习 ·

老鸟给予Java初学者的学习路线的一些建议

java学习这一部分其实也算是今天的重点,这一部分用来回答很多群里的朋友所问过的问题,那就是我你是如何学习Java的,能不能给点建议?今天我是打算来点干货,因此咱们就不说一些学习方法和技巧了,直接来谈每个阶段要学习的内容甚至是一些书籍。这一部分的内容,同样适用于一…
暂无图片
编程学习 ·

将现有Vue项目改为electron桌面端

零、前言之前看了看electron-vue,感觉还是存在一些问题的,比如electon的版本特别特别低,不能忍受。且如果你是用vue搭建的项目,最后希望能够打包成桌面端,其实很简单。一、基本步骤(1)创建vue项目、并进行开发vue create vueDemo(2)突然一天我想打包成桌面程序了// 进…
暂无图片
编程学习 ·

java之父詹姆斯高斯林的传奇人生

Java之父詹姆斯高斯林的传奇故事 詹姆斯高斯林 (James Gosling)是一名软件专家,1955年5月19日出生于加拿大,Java编程语言的共同创始人之一,一般公认他为“Java之父”。 1977年获得了加拿大卡尔加里大学计算机科学学士学位,1983年获得了美国卡内基梅隆大学计算机科学博士学…
暂无图片
编程学习 ·

Java之父 詹姆斯·高斯林 传奇的一生

Java之父 传奇的一生 Java之父 詹姆斯高斯林 詹姆斯高斯林 (James Gosling)是一名软件专家,1955年5月19日出生于加拿大,Java编程语言的共同创始人之一,一般公认他为“Java之父”。 1977年获得了加拿大卡尔加里大学计算机科学学士学位,1983年获得了美国卡内基梅隆大学计算…
暂无图片
编程学习 ·

从永远到永远-SpringCloud项目实战(七)-前端框架NUXT

1、什么是服务端渲染 服务端渲染又称SSR (Server Side Render)是在服务端完成页面的内容,而不是在客户端通过AJAX获取数据。 服务器端渲染(SSR)的优势主要在于:更好的 SEO,由于搜索引擎爬虫抓取工具可以直接查看完全渲染的页面。 如果你的应用程序初始展示 loading 菊花图,…
暂无图片
编程学习 ·

从word中复制内容包含图片到百度ueditor编辑器中

1.4.2之后官方并没有做功能的改动,1.4.2在word复制这块没有bug,其他版本会出现手动无法转存的情况本文使用的后台是Java。前端为Jsp(前端都一样,后台如果语言不通得自己做 Base64编码解码)因为公司业务需要支持IE8 ,网上其实有很多富文本框,效果都很好。例如www.wangEdi…
暂无图片
编程学习 ·

FeignClient实现跨服务之间调用

首先在A服务写好接口新建这几个包跟类@FeignClient(contextId = "remoteSysDictService", value = ServiceNameConstants.AMS_SERVICE, fallbackFactory = RemoteSysDictServiceFallbackFactory.class) public interface RemoteSysDictService {@GetMapping("/s…
暂无图片
编程学习 ·

Eclipse中Java文件图标由实心J变成空心J的问题

这里写自定义目Eclipse中Java文件图标由实心J变成空心J的问题录标题 在eclipse中空心J的java文件,表示不被包含在项目中进行编译,而是当做资源存在项目中。例如 当是单个文件为空心J的时候 1.右击该文件 – >BuildPath -->Include (如果没有includ这个选项可以采用别…
暂无图片
编程学习 ·

OSPF多区域配置

OSPF多区域配置 实验背景实验需求1.配置IP地址2.完整配置ospf多区域3.查看邻居关系4.强制发布默认路由5.在R3的G0/0/1口配置静默接口6.验证路由表1.配置ip地址 R1 [R1]INT LOOPBACK 0 [R1-LoopBack0]IP ADDRESS 1.1.1.1 32 [R1]INT G 0/0/0 [R1-GigabitEthernet0/0/0]IP ADDRES…
暂无图片
编程学习 ·

springboot通过Aop面向切面实现彩色日志

通过springboot的Aop面向切面实现彩色日志使用的场景Spring Boot是由Pivotal团队提供的全新框架,其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置,从而使开发人员不再需要定义样板化的配置。通过这种方式,Spring Boot致力于在蓬…
暂无图片
编程学习 ·

JVM堆_jprofile初次使用_OOM初识(有想法随时更新)

堆相关信息的查看 package JVMHere;public class TestFirst {public static void main(String[] args) {//返回虚拟机试图使用的最大内存long max = Runtime.getRuntime().maxMemory(); //字节 1024 * 1024//返回JVM的总内存long total = Runtime.getRuntime().totalMemory();…
暂无图片
编程学习 ·

HTTPS单向/双向认证

HTTPS单向/双向认证基本概念原理单向认证流程双向认证流程 基本概念keystore: keytool生成证书的存储库,用来存储若干条目(证书),每一条目包含公私钥,主体信息等。默认为用户目录下.keystore,相当于一个有密码保护的文件。 truststore: 与keystore格式相同,只是为区分key…
暂无图片
编程学习 ·

微信小程序——request封装/promise,async封装request

一,request封装 1,在根目录utils下创建一个index.js文件,用来写封装的request2,创建config/index.js来放我们的基础路径3,utils/index.jsimport {BASEURL} from ../config/index;//引入基础路径 export function $get(url,success){ $request(url,GET,success) } export fun…
暂无图片
编程学习 ·

【每天一道leetcode】简单 - 13. 罗马数字转整数

文章目录解法一代码思路 用户输入罗马数字,程序输出对应的阿拉伯数字,题目具体信息见正文内链接。题目链接:https://leetcode-cn.com/problems/roman-to-integer/ 涉及到的知识:hashmap enum switch 控制台输入输出解法一 代码 import java.io.InputStream; import java.io…