Day6-T3
2024-09-05 11:00:04
原题目
某个帝国修了一条非常非常长的城墙来抵御外敌,城墙共分N段,每一段用一个整数来描述坚固程度。
过了几年,城墙年久失修,有很多段都己经损坏,于是皇帝决定派你去修理城墙,但是经费有限.
所以你准备先考察一下城墙如果一段连续的城墙它们的坚固程度之和>0,邵么我们认为这段城墙暂时有效。
例如
5
-5 1 - 3 2 3
这段城墙共分5段,坚固程度之和=1.要比0大,我们认为它还算有效
下面告诉你N段城墙的坚固情况。
请你求出最长的一段连续的城墙,要求坚固程度之和>0
第1行是一个数N。
第2行共N个整数,Ai描述第i段城墙的坚固程度:
输出共一行一个整数,最长的一段连续城墙的长度;
S1:
Input:
- - - - -
Output:
Describe:维护一个前缀和单调减的队列,保证后面减前面[也就是sum[l->r]]为正。
code:
#include<bits/stdc++.h>
#define rep(a,b) for(register int i=(a);i<=(b);i++)
#define per(a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
long long l,r,n,ans,tot,a[5959595],q[5050505],now;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=a[i-1]+read();
for(int i=1;i<=n;i++)
{
l=0,r=tot,now=0x7fffffff; //初始化
while(l<=r){ //二分,由于q是单调队列,满足单调性
long long mid=l+r>>1;
if(a[i]>a[q[mid]])now=mid,r=mid-1; //找当前值[前缀和]在q中的位置
else l=mid+1;
}
if(a[i]<a[q[tot]])q[++tot]=i; //无弹出,所以编号也满足单调减。越前面的越好,对答案的贡献越大[若在队尾加入队列]
if(now!=0x7fffffff)ans=max(i-q[now],ans); //加入ans
}
cout<<ans;
return 0;
}
最新文章
- PHP 常用框架
- MSSQL日志传送出现“LSN 太晚,无法应用到数据库”
- 虚拟化技术比较 PV HVM
- phpQuery用法
- 利用ParameterizedType获取泛型参数类型
- 构建Docker平台【第四篇】创建服务及扩缩容等操作
- python 一篇搞定所有的异常处理
- python笔记十三(高阶函数、装饰器)
- CodeForces 459C Pashmak and Buses(构造)题解
- 来了解一下Redis的分布式锁
- linux一键安装包
- android笔记:ListView及ArrayAdapter
- 使用socket编程实现一个简单的文件服务器
- 【BZOJ1509】[NOI2003]逃学的小孩 直径
- P1077
- Windows与Unix思想
- LeetCodeOJ刷题之12【Integer to Roman】
- Agri-Net - poj 1258 (Prim 算法)
- Qt5.7中使用MySQL Driver(需要把libmysql.dll文件拷贝到Qt的bin目录中。或者自己编译的时候,链接静态库)
- centos 安装 python3 分类链接
热门文章
- JavaScript - __proto__和prototype,原形
- 循环语句(while语句和do...while语句)
- VB.NET中Sub和Function的区别
- 使用KVO键值监听
- input、raw_input区别,运算符,运算优先级,多变赋值方式
- JavaScript学习笔记----- 继承的实现及其原理
- Spark教程——(7)编写spark-sql程序读取HBase定时生成报表
- 深入理解Java虚拟机-如何利用VisualVM对高并发项目进行性能分析
- ASC码速记
- 回文串[APIO2014](回文树)