51nod1437 迈克步

摘要:
isdigit)c=getchar();whilex=x*10+c-'0',c=getchar();returnx;}charsh[15];voidprint{intcnt=0;whilesh[++cnt]=x%10,x/=10;dwnputchar;putchar;}constintnmax=2e5+5;constintinf=0x7f7f7f7f;inta[nmax],ans[nmax],l[nmax],r[nmax],q[nmax];voidmaxs{if(a<b)a=b;}intmain(){intn=read();repa[i]=read();l[1]=1;intcur=1;q[1]=1;rep{while--cur;l[i]=q[cur]+1;q[++cur]=i;}r[n]=n;cur=1;q[1]=n;q[0]=n+1;dwn{while--cur;r[i]=q[cur]-1;q[++cur]=i;}repmaxs;inttmp=0;dwnmaxs,maxs;repprint;printf("");return0;}1437迈克步题目来源:CodeForces基准时间限制:1秒空间限制:131072KB分值:80难度:5级算法题收藏关注有n只熊。他们站成一排队伍,从左到右依次1到n编号。一组熊指的队伍中连续的一个子段。Input单组测试数据。第二行包含n个整数以空格分开,a1,a2,...,an,表示熊的高度。Output在一行中输出n个整数,对于x从1到n,输出组大小为x的最大力量。

傻叉单调栈

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}
char sh[15];
void print(int x){
	int cnt=0;
	while(x) sh[++cnt]=x%10,x/=10;
	dwn(i,cnt,1) putchar(sh[i]+48);
	putchar(32);
}
const int nmax=2e5+5;
const int inf=0x7f7f7f7f;
int a[nmax],ans[nmax],l[nmax],r[nmax],q[nmax];
void maxs(int &a,int b){
	if(a<b) a=b;
}
int main(){
	int n=read();rep(i,1,n) a[i]=read();
	l[1]=1;int cur=1;q[1]=1;
	rep(i,2,n){
		while(a[q[cur]]>=a[i]&&cur) --cur;
	    l[i]=q[cur]+1;q[++cur]=i;
	}
	r[n]=n;cur=1;q[1]=n;q[0]=n+1;
	dwn(i,n-1,1){
		while(a[q[cur]]>=a[i]&&cur) --cur;
		r[i]=q[cur]-1;q[++cur]=i;
	}
	rep(i,1,n) maxs(ans[r[i]-l[i]+1],a[i]);
	int tmp=0;
	dwn(i,n,1) maxs(ans[i],tmp),maxs(tmp,ans[i]);
	rep(i,1,n) print(ans[i]);printf("
");
	return 0;
}
题目来源:CodeForces
基准时间限制:1秒 空间限制:131072KB 分值:80难度:5级算法题

有n只熊。他们站成一排队伍,从左到右依次1到n编号。第i只熊的高度是ai。

一组熊指的队伍中连续的一个子段。组的大小就是熊的数目。而组的力量就是这一组熊中最小的高度。

迈克想知道对于所有的组大小为x(1 ≤ x ≤ n)的,最大力量是多少。

Input
单组测试数据。
第一行有一个整数n(1≤n≤2×10^5),表示熊的数目。
第二行包含n个整数以空格分开,a1,a2,...,an(1≤ai≤10^9),表示熊的高度。
Output
在一行中输出n个整数,对于x从1到n,输出组大小为x的最大力量。
Input示例
10
1234543216
Output示例
6443322111

免责声明:文章转载自《51nod1437 迈克步》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇3D画廊UML实践详细经典教程下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

Asp.Net开源服务端框架,WebApi后端框架(C#.NET)

本文主要介绍了基于Asp.Net平台、C#语言+SQL数据库的服务器的WebApi后端框架。K=WebApi&c=1&p=1.NETWebApi开发框架|MVC框架|后端框架|服务器框架-标准版本V1.0适用开发:快速构建支持多个客户端的服务器程序,并支持APP、B/S、c/S跨平台移动终端等。C/S系统开发框架的高级版本或更高版本支持多种后...

zookeeper 日志输出到指定文件夹

最近,我在学习ZookeperStormKafka。顺便说一下,我在本地建立了一个集群。我遇到了Zookeeper日志输出路径的问题。我发现设置log4j。Zookeeper中的属性无法解决日志路径问题。我发现解决方案如下:1.修改log4j属性,您应该能够更改它。我更改了红色粗体,但仍然没有生效。#定义要移动的默认值...

用python调用caffe时出错:AttributeError: 'module' object has no attribute 'bool_'

下面给出了一个解决方案,即重命名冲突的io文件:numpyと PyCaffe公司が io。年が 竞争す る よ で す$ pythonclassify。py--raw_scale255~/caffe/101_ObjectCategories/airaires/image_0001.jpg../result.npyTraceback:文件“classif.py...

C#Win32API编程之PostMessage

本文以C#调用Win32API函数PostMessage完成指定表单的后台鼠标和键盘模拟为例,大致解释了C#调用非托管代码和Window的消息处理机制。我们可以将PostMessage用于函数。成功与否在很大程度上取决于我们传达的信息是否真实。消息表明消息是什么。请原谅我先讲故事。我希望先解释一下PostMessage函数。这是一个异步操作,如下图所示:调用...

Ubuntu 18.04 安装微信(附企业微信)

Ubuntu软件市场也是有的,所以安全性不用担心开源地址:https://github.com/geeeeeeeeek/electronic-wechat下面介绍几种安装的方式:1.直接解压运行先选择你系统版本:解压一下:tar-zxvfxxx.tar.gz算了,还是简单为新手分析一下==》tar命令可以解包.tar和.tar.gz。为啥我的没有微信图标?...

nginx 浏览php的时候会变成下载

php的时候会变成下载:这是因为nginx没有设置好碰到php文件时,要传递到后方的php解释器。当然啦,你的php-fpm解析器也需要正常运行,并监听好9000端口,才能最终生效并有效处理php脚本。windows下开启监听的办法,php-cgi.exe-b127.0.0.1:9000-cphpphp.ini待续:。。。。。...