题目链接:http://codeforces.com/problemset/problem/332/B

题目大意:
给你n个数和一个整数k,要求找到不相交的两个长度为k的区间,使得区间和最大,输出这两个区间的起点。
解题思路:
先计算前缀和,然后预处理出maxsum[i],maxsum[i]记录i~n最大的长度为k子段的和。
然后再去枚举即可。

 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<cctype>
#include<math.h>
#include<stdlib.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define lc(a) (a<<1)
#define rc(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define _for(i,start,end) for(int i=start;i<=end;i++)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const int N=5e6+;
const LL INF64=1e18;
const int INF=0x3f3f3f3f;
const double eps=1e-; LL sum[N]; //记录前缀和
LL maxsum[N]; //maxsum[i]记录i~n最大的长度为k子段的和
int idx[N]; //idx[i]记录相应的i~n最大子段的起点 int main(){
FAST_IO;
int n,k;
cin>>n>>k;
for(int i=;i<=n;i++){
cin>>sum[i];
sum[i]+=sum[i-];
}
int lim=n-k+;
for(int i=lim;i>=;i--){
LL now=sum[i+k-]-sum[i-]; //now为i~i+k-1之和
if(now>=maxsum[i+]){ //因为要保证答案字典序最小,所以下标往小的取
maxsum[i]=now;
idx[i]=i;
}
else{
maxsum[i]=maxsum[i+];
idx[i]=idx[i+];
}
} int st1=,st2=k+;
LL mmax=sum[*k];
for(int i=;i<=lim-k;i++){
LL now=sum[i+k-]-sum[i-];
if(now+maxsum[i+k]>mmax){ //maxsum[i+k]为i+k~n最大的长度为k的子段和
mmax=now+maxsum[i+k];
st1=i,st2=idx[i+k];
}
}
cout<<st1<<" "<<st2<<endl;
return ;
}

最新文章

  1. 67. Add Binary
  2. Qt 学习之路 :菜单栏、工具栏和状态栏
  3. Haskell趣學指南--这个有意思
  4. js实现搜索框响应回车键
  5. api接口json串换行
  6. 暑假练习赛 006 A Vanya and Food Processor(模拟)
  7. Splay伸展树入门(单点操作,区间维护)附例题模板
  8. 如何设计一个restful风格的API
  9. React项目中跨域问题的解决方案
  10. Android自定义万能Canvas画布
  11. HIbernate处理数据更新丢失
  12. C++ delegate的几种方法
  13. Mock.js的简单使用
  14. 手动创建binary log files和手动编辑binary log index file会有什么影响
  15. k8s问题收集
  16. python爬虫实践教学
  17. 洛谷P2059 卡牌游戏 [JLOI2013] 概率dp
  18. 第13章 TCP编程(2)_TCP的连接和关闭过程
  19. mongoDB学习第二天之常用方法
  20. Javascript实现简单的选项卡

热门文章

  1. EndNote文献悬挂缩进的设置方法及设置参考文献序号后面空格长度
  2. Excel 中 VLOOKUP() 函数小结
  3. 笔记 jquery 的一个bug解决方法积累
  4. linux下安装shellinabox实现web登录服务器
  5. oracle表结构和数据导出时的一些勾选项说明
  6. Codeforces Round #477 (rated, Div. 2, based on VK Cup 2018 Round 3) D 贪心
  7. hbase系列之:初识hbase
  8. JS日历,可获得指定日期周数及星期几
  9. Linux学习4-信号
  10. 微服务深入浅出(6)-- 熔断器Hystrix