带了一个转化的单调队列裸题。

转化为前缀和相减即可。

有一点需要注意:从0开始入队而不是1,因为要统计第一个。

(从网上找的对拍程序,结果别人写错了)

 /**
freopen("in.in", "r", stdin);
freopen("my.out", "w", stdout);
*/
//// /////////////////////////////
#include <cstdio>
const int N = ; int a[N], sum[N], Q[N], t, e = ; inline void max(int &a, const int b) {
if(a < b) a = b;
return;
} int main() {
//freopen("in.in", "r", stdin);
//freopen("my.out", "w", stdout);
int n, M;
scanf("%d%d", &n, &M);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
sum[i] = sum[i - ] + a[i];
} /*
for(int i = 1; i <= n; i++) {
printf("%d ", sum[i]);
}
printf("\n");
*/ int ans = -0x3f3f3f3f;
for(int i = ; i <= n; i++) { /// !! 0
Q[++t] = i;
if(Q[e] < i - M) {
e++;
}
max(ans, sum[i] - sum[Q[e]]);
while(e < t && sum[i] <= sum[Q[t - ]]) {
Q[--t] = i;
}
}
printf("%d", ans);
return ;
}

AC代码

最新文章

  1. Debian自带浏览器IceWeasel的中文化
  2. 编译cscope-15.8a遇到的问题与解决方案
  3. aspx与ascx,ashx的用法详细的总结介绍
  4. 【张泽华】android视频教程下载地址及上课源代码
  5. Android Studio 完美修改应用包名
  6. Jenkins + robot framework + git持续集成
  7. 【分享】bootstrap学习笔记
  8. spring @Component
  9. hibernate MTM 联合主键
  10. 前端利用百度开发文档给的web服务接口实现对某个区域周边配套的检索
  11. L2-001 紧急救援 (25 分) (最短路+路径打印)
  12. 遍历文件路径python版,java版
  13. [EasyUI]确认删除
  14. pytorch解决鸢尾花分类
  15. 设置div 高度 总结
  16. Jsp九大内置对象和4大作用域
  17. Hive 2.1.1安装配置
  18. 高通QMI协议
  19. Java基础(六):继承
  20. DCI改进,发布后作业乱码不能打开

热门文章

  1. spring AOP的用法
  2. 在layui中使用ajax不起作用
  3. 给定一个数组,求如果排序之后,相邻两数的最大差值,要求时间复杂度为O(N),且要求不能用非基于比较的排序
  4. kibana——es的批量操作
  5. ASP.NET4.0所有网页指令
  6. 莫烦theano学习自修第五天【定义神经层】
  7. Ajax之Jquery封装使用举例
  8. 【README.md】Markdown语言常用语法
  9. hdu-5536(字典树)
  10. Civil 3D 二次开发 翻转曲面高程分析颜色