首页 > 代码库 > HDU 3415

HDU 3415

求前i个数的和,当到j时,即是求sj-si,得i-j的和。只要求前面的si最小即可。此处可以用单调队列维护。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define N 200500using namespace std;int num[N];struct node{	int v;	int pos;}Node[N];int head,tail;void addsmall(int v,int pos,int k){	while(head<tail){		if(v<Node[tail-1].v)		tail--;		else break;	}	Node[tail].v=v; Node[tail++].pos=pos;	if(pos-Node[head].pos>=k)	head++;}int main(){	int n,k,T;	scanf("%d",&T);	while(T--){		num[0]=0;		scanf("%d%d",&n,&k);		for(int i=1;i<=n;i++){			scanf("%d",&num[i]);		}		for(int i=n+1;i<=n+k-1;i++){			num[i]=num[i%n];		}		for(int i=1;i<=n+k-1;i++){			num[i]+=num[i-1];		//	cout<<num[i]<<endl;		}		int Max=-99999999; head=0; int start=0; int end=0;		Node[0].v=0; Node[0].pos=0; tail=1;		for(int i=1;i<=n+k-1;i++){			if(Max<num[i]-Node[head].v){				start=((Node[head].pos+1)%n)==0?n:(Node[head].pos+1)%n;				end=i%n==0?n:i%n;				Max=num[i]-Node[head].v;			}			addsmall(num[i],i,k);		}		printf("%d %d %d\n",Max,start,end);	}	return 0;}

  

HDU 3415