UVALive 6609（Minimal Subarray Length）维护递增序列|RMQ - c++编程基础

题意：给一个整数序列（可能有负数），求最短的连续序列使得序列之和大于等于整数x；

解法：第一种是On的复杂度：

我们要的是sum[j]-sum[i]>=x，如果有两个决策j < j'，而且sum[j] >= sum[j']，那么j就是没用的。即维护一个sum[j]递增序列。然后每次可以二分查找，但是这里有个特点就是要得到最近的，可以同时维护一个left指针，left指针用于跟进更行答案的左边界，因为维护的单调栈不会再右移到left左边去了（因为如果left右边还可以更新的答案肯定没有当前的小了）。

第二种是RMQ的做法，比较好理解：枚举i，然后求sum[j]-sum[i]>=x最小的j，那么就二分查找j。总复杂度nlogn

第一份代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=500100; const int INF=1000000007; int n,x; LL num[Max]; LL que[Max]; LL sum[Max]; int increase[Max]; int main() { int t;cin>>t; while(t--) { scanf("%d%d",&n,&x); for(int i=1;i<=n;i++) { scanf("%lld",num+i); sum[i]=sum[i-1]+num[i]; } int right=1; increase[0]=1; int left=0; int ans=n+1; for(int i=2;i<=n;i++) { while(right>left&&sum[increase[right-1]]>=sum[i]) right--; increase[right++]=i; while(right>left+1&&sum[i]-sum[increase[left]]>=x) { ans=min(ans,i-increase[left]); left++; } } if(ans==n+1) cout<<"-1\n"; else cout<
              
               第二份代码： 
                
                
               /******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
                
                 
#include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                         #include 
                         
                           #include 
                          
                            #include 
                           
                             //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=500100; const int INF=1000000007; int n,x; LL dp[Max][30]; int mm[Max]; //初始化RMQ, b数组下标从1开始，从0开始简单修改 void RMQ(int n,LL b[]) { mm[0] = -1; for(int i = 1; i <= n; i++) { mm[i] = ((i&(i-1)) == 0) mm[i-1]+1:mm[i-1]; dp[i][0] = b[i]; } for(int j = 1; j <= mm[n]; j++) for(int i = 1; i + (1<
                            
                             >t; while(t--) { scanf("%d%d",&n,&x); for(int i=1; i<=n; i++) scanf("%lld",num+i),sum[i]=sum[i-1]+num[i]; RMQ(n,sum); int ans=n+3; for(int i=0; i
                             
                              =x) r=mid; else l=mid+1; } if(sum[r]-sum[i]>=x) ans=min(ans,r-i); if(sum[l]-sum[i]>=x) ans=min(ans,l-i); } if(ans==n+3) ans=-1; cout<