题目链接:Click
here~~
前几天学的单调队列,然后找题目练习,看这道题两天了,终于想通了。
题意:
给你一个循环序列{An},让你找出长度不大于K的连续子序列,使这个子序列和最大。
解题思路:
由于子序列连续,所以和上道题目一样,它的和可以通过两个前缀和作差得到。(即sum[i~j]=sum[j]-sum[i-1](j-i+1<=k))
而对于同一个序列终点来说,起点左边那个元素的前缀和越小,所得到的和越大。
所以,题目又变成了求滚动区间的最小值问题。
#include <stdio.h>
#include <limits.h>
const int M = 100001<<1;
int sum[M],q[M];
int main()
{
int z,n,k;
scanf("%d",&z);
while(z--)
{
int start,end,max;
int head,rear;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&sum[i]);
sum[i+n] = sum[i];
}
for(int i=2;i< n+k;i++)
sum[i] += sum[i-1];
head = rear = 0;
q[head] = 0;
max = INT_MIN;
for(int i=1;i< n+k;i++) //枚举每个区间终点
{
while(head<=rear && sum[i-1]<=sum[ q[rear] ])
rear--;
q[++rear] = i-1;
if(q[head]+1 < i-k+1) //起点如果大于区间范围,删除队首
head++;
if(sum[i] - sum[ q[head] ] > max)
{
start = q[head]+1;
end = i;
max = sum[i] - sum[ q[head] ];
}
}
end = end>n ? end%n : end;
printf("%d %d %d\n",max,start,end);
}
return 0;
}
分享到:
相关推荐
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
杭电组合博弈课件
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
杭电acm1297 #include<stdio.h> #include<string.h> #define m 1002 int f[m][70]={{1,1},{1,1},{1,2},{1,4}} void add(int p[],int q[],int sum[]) ...=10000){sum[i]-=10000 sum[i+1]++ } }
教你小小JAVA爬虫爬到HDU首页(只为学习)-附件资源
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
杭州电子科技大学online judge (hdu)第十一卷 2000 - 2099 题目集 doc 格式的,希望大家喜欢!
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高