[HDU][3415][Max Sum of Max-K-sub-sequence][线段树]

原题意思是求一个不超过 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;
}