POJ 2823 Sliding Window(线段树入门)

2024-09-07 18:08

本文主要是介绍POJ 2823 Sliding Window(线段树入门),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:

8 3
1 3 -1 -3 5 3 6 7
一串数列,有一个窗口大小为3,从数列开始往后移动,输出最大和最小值。

-1 -3 -3 -3 3 3
3 3 5 5 6 7
窗口大小为3

思路:

维护一个线段树,代码很详细

解题心得:

因为关键值的输入量有1000000,也就是叶节点有1000000个,总节点按理说是2000000-1,但这题得开3000000才能过

代码:

#include<stdio.h>
int max(int a,int b)
{return a>b?a:b;
}
int min(int a,int b)
{return a<b?a:b;
}struct Node
{int L,R;int maxn,minn;
};
Node Tree[3000000];//线段树
int a[1000001];//存输入数据
int ans_max[1000001],ans_min[1000001];//存输出数据//建树,节点为Tree[root],线段范围为l到r
void Maketree(int root,int l,int r)
{//1.给线段范围赋值Tree[root].L=l;Tree[root].R=r;//2.判断是否已经到达叶节点,若是则赋关键值并返回,否则继续延伸if(l==r){Tree[root].maxn=Tree[root].minn=a[l];//关键值即为题目要维护的元素。曾错在此处return;}else{//取要分割线段的中点int mid=(l+r)>>1;//建立左儿子Maketree(root*2,l,mid);//建立右儿子Maketree(root*2+1,mid+1,r);//根据左儿子与右儿子的关键值,更新自身关键值Tree[root].maxn=max(Tree[root*2].maxn,Tree[root*2+1].maxn);Tree[root].minn=min(Tree[root*2].minn,Tree[root*2+1].minn);return;}
}//寻找以root为根中,范围为l到r的线段的关键值,结果存在maxn与minn中
void find(int root,int l,int r,int& maxn,int& minn)
{//如果树根的线段正好满足,存结果并返回,否则往下搜索if(Tree[root].L==l&&Tree[root].R==r){maxn=Tree[root].maxn;minn=Tree[root].minn;return;}else{//取该树根线段的中点int mid=(Tree[root].L+Tree[root].R)>>1;//如果要查找的线段在树根线段中点左侧 T->L---l----r----mid--------T->Rif(mid>=r){//往左儿子寻找find(root*2,l,r,maxn,minn);}//如果要查找的线段在树根中点右侧else if(mid<l){//往右儿子寻找find(root*2+1,l,r,maxn,minn);}//如果要查找的线段在树根的左儿子和右儿子中各占一部分else{//将要查找的线段分为两部分,一部分往左儿子找,一部分往右儿子找int max1,max2,min1,min2;//存放两边各自找到的关键值,取最优//左儿子部分find(root*2,l,mid,max1,min1);//右儿子部分find(root*2+1,mid+1,r,max2,min2);//取最优更新在此树根找到的结果maxn=max(max1,max2);minn=min(min1,min2);}return;}
}int main()
{int n,k;while(~scanf("%d%d",&n,&k)){int i;for(i=1;i<=n;i++){scanf("%d",&a[i]);}Maketree(1,1,n);for(i=1;i<=n-k+1;i++){find(1,i,i+k-1,ans_max[i],ans_min[i]);}for(i=1;i<=n-k+1;i++){if(i==1) printf("%d",ans_min[i]);else printf(" %d",ans_min[i]);}printf("\n");for(i=1;i<=n-k+1;i++){if(i==1) printf("%d",ans_max[i]);else printf(" %d",ans_max[i]);}printf("\n");}return 0;
} 


这篇关于POJ 2823 Sliding Window(线段树入门)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1145775

相关文章

Python中OpenCV与Matplotlib的图像操作入门指南

《Python中OpenCV与Matplotlib的图像操作入门指南》:本文主要介绍Python中OpenCV与Matplotlib的图像操作指南,本文通过实例代码给大家介绍的非常详细,对大家的学... 目录一、环境准备二、图像的基本操作1. 图像读取、显示与保存 使用OpenCV操作2. 像素级操作3.

POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能

《POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能》ApachePOI是一个流行的Java库,用于处理MicrosoftOffice格式文件,提供丰富API来创建、读取和修改O... 目录前言:Apache POIEasyPoiEasyExcel一、EasyExcel1.1、核心特性

Python中模块graphviz使用入门

《Python中模块graphviz使用入门》graphviz是一个用于创建和操作图形的Python库,本文主要介绍了Python中模块graphviz使用入门,具有一定的参考价值,感兴趣的可以了解一... 目录1.安装2. 基本用法2.1 输出图像格式2.2 图像style设置2.3 属性2.4 子图和聚

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i

Python FastAPI入门安装使用

《PythonFastAPI入门安装使用》FastAPI是一个现代、快速的PythonWeb框架,用于构建API,它基于Python3.6+的类型提示特性,使得代码更加简洁且易于绶护,这篇文章主要介... 目录第一节:FastAPI入门一、FastAPI框架介绍什么是ASGI服务(WSGI)二、FastAP

Window Server创建2台服务器的故障转移群集的图文教程

《WindowServer创建2台服务器的故障转移群集的图文教程》本文主要介绍了在WindowsServer系统上创建一个包含两台成员服务器的故障转移群集,文中通过图文示例介绍的非常详细,对大家的... 目录一、 准备条件二、在ServerB安装故障转移群集三、在ServerC安装故障转移群集,操作与Ser

Window Server2016加入AD域的方法步骤

《WindowServer2016加入AD域的方法步骤》:本文主要介绍WindowServer2016加入AD域的方法步骤,包括配置DNS、检测ping通、更改计算机域、输入账号密码、重启服务... 目录一、 准备条件二、配置ServerB加入ServerA的AD域(test.ly)三、查看加入AD域后的变

Window Server2016 AD域的创建的方法步骤

《WindowServer2016AD域的创建的方法步骤》本文主要介绍了WindowServer2016AD域的创建的方法步骤,文中通过图文介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、准备条件二、在ServerA服务器中常见AD域管理器:三、创建AD域,域地址为“test.ly”

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin