hdu3415（单调队列）-白红宇

hdu3415（单调队列）

阅读量：6435 次

发布时间：2019-06-23

本文共 1048 字，大约阅读时间需要 3 分钟。

题目链接：

题意：一个长度为n包含正负整数的数环，即第1个的左边是第n个。从中选一个不超过k的序列,使得序列和最大，最大值相同选开始点最小的，开始点相同选长度最小的。

分析：单调队列维护在k个数之内的最小值的下标，然后一直扫一遍就行了，只要懂单调队列这题就是水题了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #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]
                
                 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); }}