qscoj#19D(单调队列)
2024-08-29 08:38:52
题目链接:http://qscoj.cn/problem/130/
题意:中文题诶~
思路:直接用单调栈搞一下就好了
代码:
#include <bits/stdc++.h>
using namespace std; const int MAXN=1e6+;
const int inf=1e9;
int sum[MAXN], q[MAXN]; int main(void){
int n, k;
while(scanf("%d%d", &n, &k)!=EOF){
for(int i=; i<=n; i++){
int x;
scanf("%d", &x);
sum[i]=sum[i-]+x;
}
sum[n+]=-inf;
int ans=, front=, rear=;
for(int i=; i<=n+; i++){
ans=max(ans, sum[i]);
if((front==rear||sum[i]>sum[q[front]])){
if(i-q[rear+]+<k){
q[++front]=i;
}else{
while(i-q[rear+]+>=k&&front>rear){
rear++;
}
q[++front]=i;
}
}else if(sum[i]<sum[q[front]]){
while(front>rear&&sum[i]<sum[q[front]]){
ans=max(ans, sum[q[front]]-sum[q[rear+]]);
front--;
}
while(i-q[rear+]+>=k&&front>rear){
rear++;
}
q[++front]=i;
}
}
printf("%d\n", ans);
}
return ;
}
最新文章
- Drop all the tables, stored procedures, triggers, constraints and all the dependencies in one SQL statement
- [LeetCode] Sort Characters By Frequency 根据字符出现频率排序
- 【HBase】HBase Getting Started(HBase 入门指南)
- mybatis+oracle添加一条数据并返回所添加数据的主键问题
- 误设PATH导致命令失效的处理
- 玲珑杯1007-A 八进制大数加法(实现逻辑陷阱与题目套路)
- 李洪强iOS经典面试题135-Objective-C
- Git reset 常见用法
- PHP ERROR : Call to undefined function curl_init()
- 【新产品发布】【EVC8001 磁耦隔离式 USB 转 RS-485】
- java实现字符串反转(原作有点错误,需要看下评论)
- linux commands ---2 ,学习vim编辑器如何使用的方法。
- bzoj 4446: [Scoi2015]小凸玩密室
- codeforces259B
- Qt 使用openGL 渲染YUV420P格式的视频
- 如何用微信小程序模仿豆瓣首页
- 面向对象设计模式纵横谈:Bridge 桥接模式(笔记记录)
- opencv3.2.0实现连续图片合成avi视频
- JS判断是否是PC端访问网站
- 【Android】17.1 Bound Services基本概念
热门文章
- P3746 [六省联考2017]组合数问题
- VC++共享文件夹
- tkinter之对话框
- ES搜索排序,文档相关度评分介绍——TF-IDF—term frequency, inverse document frequency, and field-length norm—are calculated and stored at index time.
- bytearray类型
- wordpress汇总(持续更新)
- 跨线程send message
- leetcode 191 Number of 1 Bits(位运算)
- ACM学习历程—FZU 2140 Forever 0.5(计算几何 &;&; 构造)
- 《c# 实现p2p文件分享与传输系统》 二、 设计 - 续(NAT穿透)