POJ3061 Subsequence(二分前缀和法+尺取法) - c++编程基础

二分+前缀和法

满足条件的子序列长度在(0,n)之间，sum[x+i]-sum[i]为从从第i个元素开始序列长度为x的元素的和。前缀和可在O(n)的时间内统计

sum[i]的值。再用二分找出满足条件的最小的子序列长度。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #define ll __int64 #define INF 0x3fffffff using namespace std; int sum[100005]; int a[100005]; int n,s; bool C(int x) { bool flag=false; for(int i=0;i
            
             =s) { flag=true; break; } } if(flag) return true; else return false; } int solve() { int l=0,r=n+1; while(r-l>1) { int mid=(l+r)/2; if(C(mid)) r=mid; else l=mid; } return r; } int main() { int T; //freopen("d:\\Test.txt","r",stdin); cin>>T; while(T--) { cin>>n>>s; for(int i=0;i
             
              尺取法
              





 
              （1） 设置两个指针s和t，一开始都指向数列第一个元素，此外sum=0,res=0；
 
 （2） 只要sum
                
                
 （3） 直到sum>=S，更新res=min(res,t-s)；
                
 
                
 （4） 将sum减去一个元素，s加1，执行（2）。
                
 
                
 上述流程反复地推进区间的开头和末尾，来求取满足条件的最小区间。
                
 
                
              
              #include
               
                
#include
                
                  #include
                 
                   #include
                  
                    using namespace std; int n,m; int a[100005]; void solve() { int res=n+1; int s=0,t=0,sum=0; while(true) { while(t
                   
                    n) res=0; cout<
                    
                     >T; while(T--) { cin>>n>>m; for(int i=0;i