九度 1554 区间问题

题目链接~~>

做题感悟：九度比赛时没有做出来，当时写的是前缀和 + 两层 for( ) 循环果断超时。后来就拖到现在。

解题思路：我认为做题要讲究策略，一看题目给的数据范围 ai 的绝对值小于 100，so~ 此处必有隐情，一定是用到下标类似的，想了好久才想出来果然不出我所料。

                  步入正题：先处理一下前缀和把相同的前缀和的下表记录一下存在一个数组里，这里就要用到vector<int>G[ ]  来标记了，但是前缀和有复数怎么办？不要慌，可以用map映射一下，这样就 ok了。下一步就是查找了，只需要遍历一次就可以。因为 k = sum [ i ] - sum[ j -1 ]  ( j <=  i )的话，区间就为 j ~ i   so ~> 你只需要将这个等式转化一下：sum[ i ]  = sum [ j -1 ]  + k ，现在只需要依次枚举sum[ j - 1 ] 看 sum [ i ] 是否存在 , 如果存在找一个大于等于 j 的下表就可以了。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = 0x3f3f3f3f ;
     
    
   

    

     

    
    

     

      const int MX = 10005 ;
     
    
   

    

     

    
    

     

      int sum[MX] ;// 用于存前缀和
     
    
   

    

     

    
    

     

      vector<int>G[MX] ; // 存前缀和的下标
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int n,k ;
     
    
   

    

     

    
    

     
 map<int,int>m ;
     
    
   

    

     

    
    

     
 while(~scanf("%d",&n))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       m.clear() ;
     
    
   

    

     

    
    

     
 for(int i = 0;i <= n;++i)
     
    
   

    

     

    
    

     

       G[i].clear() ;
     
    
   

    

     

    
    

     
 int r=1,x,y,num,st,end ;
     
    
   

    

     

    
    

     

       sum[0]=0 ;
     
    
   

    

     

    
    

     
 for(int i=1 ;i<=n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&sum[i]) ;
     
    
   

    

     

    
    

     

       sum[i]=sum[i-1]+sum[i] ;
     
    
   

    

     

    
    

     

       x=sum[i] ;
     
    
   

    

     

    
    

     
 if(m.find(x)==m.end()) // 这点切记！！
     
    
   

    

     

    
    

     

       m[x]=r++ ; // 对应下标
     
    
   

    

     

    
    

     

       G[m[x]].push_back(i) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 scanf("%d",&k) ;
     
    
   

    

     

    
    

     
 bool flag=false ;
     
    
   

    

     

    
    

     
 for(int i=1 ;i<=n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       y=sum[i-1]+k ;
     
    
   

    

     

    
    

     
 if(m.find(y)!=m.end())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       x=m[y] ;
     
    
   

    

     

    
    

     

       num=G[x].size() ;
     
    
   

    

     

    
    

     
 int min=INF ;
     
    
   

    

     

    
    

     
 for(int j=0 ;j<num ;j++)
     
    
   

    

     

    
    

     
 if(G[x][j]>=i&&G[x][j]-i<min) // 寻找最小下标
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       flag=true ;
     
    
   

    

     

    
    

     

       st=i ;
     
    
   

    

     

    
    

     

       min=G[x][j]-i ;
     
    
   

    

     

    
    

     

       end=G[x][j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(flag) break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(flag) printf("%d %d\n",st,end) ;
     
    
   

    

     

    
    

     
 else printf("No\n") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/23510101