原题意思是求一个不超过 k 的连续序列的和的最大值。
枚举连续序列的起点 i, 然后在 [i, i+k] 区间找一个最大值,更新答案。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max(a,b) ( (a)> (b)? (a): (b) )
#define min(a,b) ( (a)< (b)? (a): (b) )
int const N= 200010;
int dat[N], sum[N];
int n, nn, k;
struct Node{
int Max, pos;
Node(){}
Node( int a, int b ): Max(a), pos(b) {}
}tb[N<<2];
inline bool operator>( Node a, Node b ){
if( a.Max== b.Max ) return a.pos< b.pos;
return a.Max> b.Max; }
void build( int L, int R, int rt ){
if( L== R ){
tb[rt]= Node( sum[L], L );
return ;}
int mid= (L+ R)>>1;
build( L, mid, rt<<1 );
build( mid+ 1, R, rt<<1|1 );
tb[rt]= max( tb[rt<<1], tb[rt<<1|1] );
}
Node query( int a, int b, int L, int R, int rt ){
if( a== L && b== R ) return tb[rt];
int mid= (L+ R)>>1;
if( b<= mid ) return query( a, b, L, mid, rt<<1 );
else if( a> mid ) return query( a, b, mid+ 1, R, rt<<1|1 );
else{
Node x= query( a, mid, L, mid, rt<<1 );
Node y= query( mid+ 1, b, mid+ 1, R, rt<<1|1 );
return max(x,y);
}
}
inline int read(){
char ch;
int d, flag= 1;
while( ch= getchar(), ch== ' ' || ch== '\n' );
if( ch== '-' ) { flag= -1; d= 0; }
else{ d= ch- '0'; }
while( ch= getchar(), ch>= '0' && ch<= '9' )
d= d* 10+ ch- '0';
return d* flag;
}
int main(){
int test;
scanf("%d",&test );
while( test-- ){
scanf("%d%d",&n,&k );
for( int i= 1; i<= n; ++i ){
dat[i]= read();
dat[i+ n]= dat[i];
}
sum[0]= 0; nn= n<<1;
for( int i= 1; i<= nn; ++i )
sum[i]= sum[i-1]+ dat[i];
build( 1, nn, 1 );
int ans= -0x7fffffff, posx= 0, posy= 0;
for( int i= 0; i<= n; ++i ){
int t= min( i+ k, nn );
Node tmp= query( i+ 1, t, 1, nn, 1 );
if( tmp.Max- sum[i]> ans ){
ans= tmp.Max- sum[i];
posx= i+ 1;
posy= tmp.pos;
}
}
printf("%d %d ", ans, posx );
if( posy> n ) printf("%d\n", posy- n );
else printf("%d\n", posy );
}
return 0;
}
分享到:
相关推荐
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
hdu 1166线段树代码
其中一类查询要求 更新 数组 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 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
hdu 1166线段树
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
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首页(只为学习)-附件资源