poj 2823 单调队列 入门 代码附注释_pojorg代码-程序员宅基地

技术标签: 单调队列  ACM/ICPC  

关于单调队列的介绍请移步:http://xuyemin520.is-programmer.com/posts/25964

结合poj2823理解比较好:http://poj.org/problem?id=2823

代码如下(跑得比较慢):

#include <cstdio>
const int Maxn=1000000+100;
    int n,k;
int id[Maxn],minn[Maxn],maxn[Maxn],date[Maxn];
void Min()
{
    int first=1,last=1;
	id[last++]=1;//第一个先初始化
	minn[1]=date[1];
	for(int i=2;i<=n;i++)
	{
	    while(date[id[last-1]]>date[i]&&first<last)//尾删除。通过索引(id[last-1])间接找到当前索引的值date[]
			last--;
		id[last++]=i;//必须在尾删除后更新尾索引值。
		while(id[first]<i-k+1)//对首删除。超出i-k+1就删除。//下同。
			first++;
		minn[i]=date[id[first]];
	}
}
void Max()
{
    int first=1,last=1;
	id[last++]=1;
	maxn[1]=date[1];
	for(int i=2;i<=n;i++)
	{
	    while(date[id[last-1]]<date[i]&&first<last)
			last--;
		id[last&
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u012915516/article/details/19054953

智能推荐

PHP+Mysql 实现留言板_html+php+mysql 实现留言板-程序员宅基地

文章浏览阅读911次。最近看了下PHP基础语法,就想利用这些基本东西实现留言板,也是对基础知识的一个巩固。什么是留言板?一种可以用来记录,展示文字信息的载体。现切入正题,说说本次留言板是怎么实现!首先用户提交留言后,相关内容存入服务器,当他想看的时候后台再把所有留言读出来,最后显示在浏览器上,用户就可以看到留言了。这其中后台需要便于读写数据的一个工具,我选择MySQL数据库来帮助_html+php+mysql 实现留言板

01.初识数据库_select user,host,password from-程序员宅基地

文章浏览阅读339次。01.初识数据库1. 数据库管理软件的由来基于我们之前所学,数据要想永久保存,都是保存于文件中,毫无疑问,一个文件仅仅只能存在于某一台机器上。如果我们暂且忽略直接基于文件来存取数据的效率问题,并且假设程序所有的组件都运行在一台机器上,那么文件存取数据并没有问题。很不幸,这显然不现实,上述假设存在以下几个问题1.1. 程序所有的组件就不可能运行在一台机器上因为这天台机器一旦挂掉则意味着整个软件的崩溃,并且程序的执行效率依赖于继承它的硬件,而一台机器的性能垂直进行扩展是有限的。于是我们只能通过水平_select user,host,password from

javaswing jtextpane 英文中文自动换行-程序员宅基地

文章浏览阅读1.7k次,点赞3次,收藏6次。最近一段时间在做一个类似QQ聊天的工具。但是在其中遇到一个问题。在做气泡聊天的时候,原本已经用Jtextarea已经实现。后来因为使用到emoji表情,需要将组件改为JtextPane来实现插入图片,改组件后出现了这样的问题 1:使用jtextpane的时候当输入的全部都是英文和数字的时候是不会自动换行。只有中文的时候才会 当出现这样的问题后上网搜索到的解决方案是:t..._jtextpane.read 中文

112家互联网与IT公司薪水一览表_网游公司薪水和其它it公司比较-程序员宅基地

文章浏览阅读1.9k次。112家互联网与IT公司薪水一览表 网传各大公司的待遇如下,吐血奉献,公司比较全。以下绝对是各大公司2013届校招的数据,少数几个是2011、2012的数据,都已经特别注明,数据真实重要性高于一切!选进来的都是已经确认的信息,放心参考。这里所说的待遇全部为税前,另外,年薪不是简单的*12,因为有年终奖。而互联网公司的待遇package,都是包含了年终奖的。以下待遇无特别说明_网游公司薪水和其它it公司比较

Kubernetes v1.22.1部署报错3:registry.aliyuncs.com/google_containers/coredns:v1.8.4...-程序员宅基地

文章浏览阅读1.1w次,点赞3次,收藏7次。环境介绍:master 192.168.2.18node1 192.168.2.19node2 192.168.2.20CentOS 7.5Docker 19.03.132核+CPU,2GB+内存报错信息: 初始化Kubernetes时出现下面报错[root@k8s-master ~]# kubeadm init --kubernetes-version=v1.22.1 --apiserver-advertise-address=192.168.1.18 --pod-network-c

Java中IO流的使用规则_io流安全使用原则-程序员宅基地

文章浏览阅读447次。Java IO 的一般使用原则 : 一、按数据来源(去向)分类:1 、是文件: FileInputStream, FileOutputStream, ( 字节流 )FileReader, FileWriter( 字符 )2 、是 byte[] : ByteArrayInputStream, ByteArrayOutputStream( 字节流 )3 、是 Char[]: CharArra..._io流安全使用原则

随便推点

centos 安装 openocd_centos安装open3d-程序员宅基地

文章浏览阅读563次。下载解压配置之前先安装跟libusb有关的库接着./configuremakemake install默认安装位置在 /usr/local/bin下面,所有PATH不用设置_centos安装open3d

SqlHelper:_sqlcommand command = createcommand(conn, "addcusto-程序员宅基地

文章浏览阅读404次。//---- SqlHelper- -主角要出场了- -怎么说呢下面的这个我看还不错哈 CreateCommand创建命令#region CreateCommand创建命令 /**//// /// 创建一个由存储过程提供的命令 /// /// /// e.g.: /// SqlCommand co_sqlcommand command = createcommand(conn, "addcustomer", "customerid", "customername");

深入理解字符串处理:从Leetcode实践出发(题号28、30、68、722、214、1392)_图像算法中的数学-程序员宅基地

文章浏览阅读1.2w次,点赞7次,收藏10次。字符串类型可以看作是特殊的数组,是一种由字符组成的数组。字符串处理在现实应用中大量存在,例如用户的姓名、文章的标题、服务器的IP地址等都以字符串形式存在。LeetCode中的字符串处理题目往往比较不容易总结出固有套路,而呈现出各自不同的处理方式,且它们在实现上都比较繁琐。唯一能总结出套路的字符串题目则是与KMP算法相关的,但这种类型的题目数量不多,而且理解这个算法本身对于很多人来说是比较困难的_图像算法中的数学

ubuntu两个显示器只出一个_当我只有一台显示器时,Ubuntu会检测到两台显示器....-程序员宅基地

文章浏览阅读1.5k次。问题:当我只有1个时,Ubuntu会检测到2个监视器. 由于引导默认情况下检测到2个监视器的默认设置有问题,因此这引起了问题,因为它在1个显示器中创建了一个镜像. 输出是一个虚拟显示器,我需要删除它,因此它将引导至LVDS1而不是镜像.关于如何永久删除VGA1的建议?:~$ xrandr -qScreen 0: minimum 320 x 200, current 1920 x 1080, max..._ubuntu只能识别一个显示器

[乐意黎原创] 万网 空间上传文件0字节的解决方法_网站空间上传文件0kb的原因-程序员宅基地

文章浏览阅读3k次。万网空间上传文件0字节的解决方法,这种情况可能是您的网站空间满导致,您可以通过ftp方式登陆,会出现相应的网站空间使用的信息,或者可以登陆万网空间控制面,看看您的空间使用情况,或者删除一些无用或过期的文件释放一些网站空间,然后再上传新的内容。或者您可以和万网互联销售部联系升级您的网站,以便获取更多的网站空间。 更多问题你可以咨询我们的在线客服人员。_网站空间上传文件0kb的原因

Matlab实现mRMR-CNN-LSTM-Mutilhead-Attention最大相关最小冗余特征选择卷积长短期记忆神经网络融合多头注意力机制多特征分类预测 2023新算法,直接写!-程序员宅基地

文章浏览阅读848次,点赞34次,收藏20次。柴油机故障诊断是保证柴油机安全稳定运行的关键技术。本文提出了一种基于最大相关最小冗余特征选择(mRMR)、卷积长短期记忆神经网络(CNN-LSTM)和多头注意力机制(Mutilhead-Attention)的柴油机故障诊断方法(mRMR-CNN-LSTM-Mutilhead-Attention)。该方法首先利用mRMR算法从原始信号中提取相关性高、冗余性低的最优特征子集。然后,使用CNN-LSTM网络对提取的特征进行时域和频域特征提取。