热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

2021-2022ACM集训队月度编程挑战赛第二轮:最大值与最小值的选择

在2021-2022ACM集训队月度编程挑战赛第二轮中,题目“最大值与最小值的选择”要求参赛者处理一个包含n个元素的数组,并给定一个整数k。任务是通过选择特定的子数组,计算并返回这些子数组的最大值和最小值之间的差值。该问题考验了选手对数组操作和优化算法的理解与应用能力。

F: max or min

题意:
给你一个n个数的数组和一个k给你一个n个数的数组和一个knk
1<&#61;n,k<&#61;1e5,1 <&#61; n , k <&#61; 1e5 ,1<&#61;n,k<&#61;1e5,
a1,a2,......ana1,a2,......ana1,a2,......an
1<&#61;ai<&#61;n1 <&#61; ai <&#61; n1<&#61;ai<&#61;n
求一个最长区间[l,r]求一个最长区间[l,r][l,r]
满足这个区间的最大值−最小值<&#61;k满足这个区间的最大值-最小值<&#61;k<&#61;k
思路&#xff1a;
假设当前区间为mid假设当前区间为midmid
如果存在长度为mid的区间满足最大值−最小值<&#61;k如果存在长度为mid的区间满足最大值-最小值<&#61;kmid<&#61;k
说明mid可以变大说明mid可以变大mid
否则mid变小否则mid变小mid

因此考虑二分查找mid因此考虑二分查找midmid
时间复杂度logn时间复杂度lognlogn

查询区间最大值和最小值可以考虑查询区间最大值和最小值可以考虑
树状数组/st表/线段树树状数组/st表/线段树/st/线

线段树查询nlogn总时间复杂度nlognlogn线段树查询nlogn总时间复杂度nlognlogn线nlognnlognlogn
st表查询o1总时间复杂度nlognst表查询o1总时间复杂度nlognsto1nlogn
树状数组与线段树类似树状数组与线段树类似线

其实还有个很妙的做法其实还有个很妙的做法
set&#43;双指针动态维护nlognset&#43;双指针动态维护 nlognset&#43;nlogn
每次假设i这个下标为区间右端点每次假设i这个下标为区间右端点i
找到最大的一个左端点找到最大的一个左端点
同时更新答案同时更新答案
方法一方法一
时间复杂度&#xff1a;线段树&#43;二分Onloglogn线段树&#43;二分Onloglogn线&#43;Onloglogn

#include
#include
#include
#include using namespace std;const int N &#61; 200010;int n , m , k ;
struct Node
{int l, r;int v , minv ; // 区间[l, r]中的最大值和最小值
}tr[N * 4];
int a[N];void pushup(int u) // 由子节点的信息&#xff0c;来计算父节点的信息
{tr[u].v &#61; max(tr[u<<1].v,tr[u<<1|1].v);tr[u].minv &#61; min(tr[u<<1].minv,tr[u<<1|1].minv);
}void build(int u, int l, int r)
{if(l &#61;&#61; r) tr[u] &#61; {l,r,a[r],a[r]};else{tr[u] &#61; {l, r};int mid &#61; r &#43; l >> 1 ;build(u << 1 , l , mid ) , build(u << 1 | 1 , mid &#43; 1 , r);pushup(u);}
}int query(int u, int l, int r)
{if(tr[u].l >&#61; l && tr[u].r <&#61; r) return tr[u].v ;int v &#61; -1e9 ;int mid &#61; tr[u].l &#43; tr[u].r >> 1 ;if(l <&#61; mid) v &#61; max(v,query(u << 1 , l ,r));if(r > mid) v &#61; max(v,query(u << 1 | 1 , l , r));return v ;
}int query1(int u, int l, int r)
{if(tr[u].l >&#61; l && tr[u].r <&#61; r) return tr[u].minv ;int v &#61; 1e9 ;int mid &#61; tr[u].l &#43; tr[u].r >> 1 ;if(l <&#61; mid) v &#61; min(v,query1(u << 1 , l ,r));if(r > mid) v &#61; min(v,query1(u << 1 | 1 , l , r));return v ;
}bool check(int mid)
{int x &#61; mid ;for(int i &#61; 1 ; i &#43; x - 1 <&#61; n ; i &#43;&#43;){if(query(1,i,i&#43;x-1) - query1(1,i,i&#43;x-1) <&#61; k) return true ;}return false ;
}int main()
{cin >> n >> k ;for(int i &#61; 1 ; i <&#61; n ; i &#43;&#43;) scanf("%d",&a[i]);build(1,1,n);int l &#61; 1 , r &#61; n ;while(l < r){int mid &#61; r &#43; l &#43; 1 >> 1 ;if(check(mid)) l &#61; mid ;else r &#61; mid - 1 ;}cout << l << "\n" ;return 0;
}

方法二方法二
时间复杂度&#xff1a;set&#43;双指针Onlognset&#43;双指针Onlognset&#43;Onlogn

#include
#define sz(x) ((int)(x).size())
using namespace std;
const int N &#61; 1e6 &#43; 10 ;int n , k ;
int a[N] ;signed main()
{cin >> n >> k ;for(int i &#61; 1 ; i <&#61; n ; i &#43;&#43;) scanf("%d",a &#43; i) ;int res &#61; 0 ;multiset<int> q ;for(int i &#61; 1 , j &#61; 1 ; i <&#61; n ; i &#43;&#43;){q.insert(a[i]) ;while(q.size() && *--q.end() - *q.begin() > k && j <&#61; n) {q.erase(q.find(a[j &#43;&#43;])) ;}res &#61; max(res,sz(q)) ;}cout << res << "\n" ;return 0;
}

方法三方法三
时间复杂度&#xff1a;st表&#43;二分Onlognst表&#43;二分Onlognst&#43;Onlogn

#include
using namespace std;
int a[100005],maxn[100005][30],minn[100005][30];
int n,k;
void st_prework(){for(int i&#61;1;i<&#61;n;i&#43;&#43;)maxn[i][0]&#61;minn[i][0]&#61;a[i];int t&#61;log(n)/log(2)&#43;1;for(int j&#61;1;j<t;j&#43;&#43;)for(int i&#61;1;i<&#61;n-(1<<j)&#43;1;i&#43;&#43;){minn[i][j]&#61;min(minn[i][j-1],minn[i&#43;(1<<(j-1))][j-1]);maxn[i][j]&#61;max(maxn[i][j-1],maxn[i&#43;(1<<(j-1))][j-1]);}
}
int getmax(int l,int r){int k&#61;log(r-l&#43;1)/log(2);return max(maxn[l][k],maxn[r-(1<<k)&#43;1][k]);
}
int getmin(int l,int r){int k&#61;log(r-l&#43;1)/log(2);return min(minn[l][k],minn[r-(1<<k)&#43;1][k]);
}
int main()
{cin>>n>>k;for(int i&#61;1;i<&#61;n;i&#43;&#43;)scanf("%d",&a[i]);st_prework();int anss&#61;0;for(int i&#61;1;i<&#61;n;i&#43;&#43;){int l&#61;i,r&#61;n;while(l<r){int mid&#61;(l&#43;r&#43;1)/2;int ans&#61;getmax(i,mid)-getmin(i,mid);if(ans<&#61;k){l&#61;mid;}else {r&#61;mid-1;}}anss&#61;max(anss,l-i&#43;1);}cout<<anss<<endl;
}


推荐阅读
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 文件描述符、文件句柄与打开文件之间的关联解析
    本文详细探讨了文件描述符、文件句柄和打开文件之间的关系,通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • 数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始,逐步掌握数据库内核开发的基础知识和实践技能,重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
author-avatar
ccM保佑加琳诺爱儿1984f
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有