树上有猴（思路）

一棵大树上初始时有若干个猴子（也可能没有）。

接下来 n个时刻，每个时刻树上猴子的数量都会发生变动。

第 i时刻的变动数量为 ai，ai>0 表示有 ai 只猴子上了树，ai<0 表示有 |ai|只猴子下了树。

已知，在任意时刻树上的猴子总数都没有超过 w，当然也不可能小于 0。

请问，初始时的猴子数量共有多少种可能性？

例如，当 n=3,w=5且 a1=2,a2=1,a3=−3 时，初始时的猴子数量可能为 0,1,2个。

输入格式

第一行包含两个整数 n,w。

第二行包含 n个整数 a1,a2,…,an。

输出格式

一个整数，表示初始时的猴子数量共有多少种可能性。

如果无解，即初始时有多少只猴子都不满足题目要求，则输出 0。

数据范围

前六个测试点满足，1≤n≤10，1≤w≤10。
所有测试点满足，1≤n≤1000，1≤w≤109，−106≤ai≤106。

输入样例1：

  

   

    

     

    
    

     

      3 5
     
    
   

    

     

    
    

     

      2 1 -3
     
    
  
 

输出样例1：

3

 

输入样例2：

  

   

    

     

    
    

     

      2 4
     
    
   

    

     

    
    

     

      -1 1
     
    
  
 

输出样例2：

4

 

输入样例3：

  

   

    

     

    
    

     

      4 10
     
    
   

    

     

    
    

     

      2 4 1 2
     
    
  
 

输出样例3：

2

 

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      const int N = 1010,inf=1e7;
     
    
   

    

     

    
    

     

      int a[1010],s[1010],mins=0,maxs=-inf;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int n,w;
     
    
   

    

     

    
    

     

          cin>>n>>w;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

              s[i]=s[i-1]+a[i];
     
    
   

    

     

    
    

     

              mins=min(s[i],mins);
     
    
   

    

     

    
    

     

              maxs=max(s[i],maxs);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    //cout<<maxs<<endl<<mins<<endl<<endl;
     
    
   

    

     

    
    

     
    if(maxs>0)maxs=w-maxs;
     
    
   

    

     

    
    

     
    else maxs=w;
     
    
   

    

     

    
    

     

          mins=-mins;
     
    
   

    

     

    
    

     
    printf("%d",max(maxs-mins+1,0));
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

原文链接：blog.csdn.net/weixin_54227557/article/details/120588952