热门标签 | 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函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 本文详细介绍了Java中org.neo4j.helpers.collection.Iterators.single()方法的功能、使用场景及代码示例,帮助开发者更好地理解和应用该方法。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • Java 类成员初始化顺序与数组创建
    本文探讨了Java中类成员的初始化顺序、静态引入、可变参数以及finalize方法的应用。通过具体的代码示例,详细解释了这些概念及其在实际编程中的使用。 ... [详细]
  • 数据管理权威指南:《DAMA-DMBOK2 数据管理知识体系》
    本书提供了全面的数据管理职能、术语和最佳实践方法的标准行业解释,构建了数据管理的总体框架,为数据管理的发展奠定了坚实的理论基础。适合各类数据管理专业人士和相关领域的从业人员。 ... [详细]
  • 深入解析Spring Cloud Ribbon负载均衡机制
    本文详细介绍了Spring Cloud中的Ribbon组件如何实现服务调用的负载均衡。通过分析其工作原理、源码结构及配置方式,帮助读者理解Ribbon在分布式系统中的重要作用。 ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
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社区 版权所有