这个题比较显然,要用前缀和来做。但只用前缀和是过不去的,会TLE,所以需要进行优化。

对于每个前缀和数组 b 中的元素,都可以找到以 b[i] 结尾的子段最大值 p[i],显然,最终的 ans 就是 max(p[i]),其中 1 ≤ i ≤ n。

故可知,ans = max( p[i] ) = max( max( b[i] - b[j] ) ),其中的 max( b[i] - b[j] ) 是 p[i]。

很明显, p[i] = b[i] - min( b[j] ),其中 i-m ≤ j ≤ i-1

这时候的重点就是在小于 O(m) 的时间里找出最小的 b[j] ,若已知 min(b[j]) ,即可求出 p[i]。

因为一直要找最小的 b[j],而这个框框 m 就引得我们想到 单调队列

单调队列里面存的就是这个 “最小的b[j]” ,这样在打完表后就可以在 O(1) 的时间里查到它啦。

下面是AC代码

//P1714 切蛋糕
#include<iostream>
#include<cstdio>
#define NUM 500010
using namespace std;
int n,m;
long long p[NUM],b[NUM];//b是前缀和_
long long q1[NUM];//单调队列_
void xiao(){ //建立单调队列
int head = 1,tail = 0;//head <= tail时队列里有值_
for( int i = 1;i <= n;i++ ){
while( head <= tail && q1[head] + m <= i ) head++; //如果这个head已经过期了,就直接在队头pop
while( head <= tail && b[i] < b[q1[tail]] ) tail--;
q1[++tail] = i;
if( i >= m ) p[i] = b[q1[head]];
}
}
int main(){
ios::sync_with_stdio(0);//关同步,这样输入可以快一点(因为我不想打快读)
cin >> n >> m;
for( int i = 1;i <= n;i++ ){
long long x;
cin >> x;
b[i] = b[i-1] + x;//数组b存前缀和
}
xiao();//建立单调队列
long long ans = b[1];//因为我们下一行的i是从m开始枚举,要是直接ans = -1,就会在第6个测点卡住
for( int i = m;i <= n;i++ )
if( ans < b[i] - p[i] ) ans = b[i] - p[i];
cout << ans;
return 0;
}

最新文章

  1. Javascript绝不要使用在文档加载之后使用 document.write(), 怎么理解?
  2. 转:解决apache的the requested operation has failed
  3. 【BZOJ 3223】文艺平衡树 模板题
  4. Asp.Net 常用代码-备用
  5. node开发 npm install -g express-generator@4
  6. Magento模型和ORM基础
  7. escape character.
  8. 关于js对象引用的小例子
  9. 大数据工具篇之Hive与MySQL整合完整教程
  10. Jquery控制点击时一、二级菜单自由隐藏与出现
  11. Python 装饰器总结
  12. Python3实现QQ机器人自动爬取百度文库的搜索结果并发送给好友(主要是爬虫)
  13. win8和win7下解决php5.3和5.4、5.5等不能加载php_curl.dll的终极解决办法 收藏
  14. poj3237树链剖分边权+区间取负
  15. 图片通过Base64Coder编码、解码
  16. 从jar包还原出java源码(项目文件)
  17. openssl生成证书
  18. CSU - 2061 Z‘s Coffee
  19. poj 2195 Going Home(最小费最大流)
  20. js经典试题之原型与继承

热门文章

  1. Vagrant详细教程
  2. wireshark、tcpdump使用笔记
  3. es篇-es基础
  4. 服务器安全加固 - Linux
  5. Java多线程—线程同步(单信号量互斥)
  6. 这些 Shell 分析服务器日志命令集锦,收藏好
  7. 干货|SQL语句大全,所有的SQL都在这里了(建议收藏)
  8. 运维:DevSecOps
  9. 修改Docker容器默认时区
  10. SQL中常用的字符串LEFT函数和RIGHT函数详解!