首页 > 代码库 > hdu3415（单调队列）
hdu3415（单调队列）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3415
题意：一个长度为n包含正负整数的数环，即第1个的左边是第n个。从中选一个不超过k的序列,使得序列和最大，最大值相同选开始点最小的，开始点相同选长度最小的。
分析：单调队列维护在k个数之内的最小值的下标，然后一直扫一遍就行了，只要懂单调队列这题就是水题了。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 200010using namespace std;int a[N],que[N],sum[N],l,r;int solve(int n,int k){ for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; int head,tail,mx=-1000000000; head=tail=0; que[head]=0; for(int i=1;i<=n;i++) { while(head<=tail&&i-que[head]>k)head++; int j=que[head]; if(sum[i]-sum[j]>mx) { mx=sum[i]-sum[j]; l=j+1;r=i; } while(head<=tail&&sum[i]<sum[que[tail]])tail--; que[++tail]=i; } l=l>n/2?l-n/2:l; r=r>n/2?r-n/2:r; return mx;}int main(){ int t,n,k; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i]; int mx=solve(2*n,k); printf("%d %d %d\n",mx,l,r); }}
hdu3415（单调队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。