钓鱼

Description

有个机器人去钓鱼，一天下来24小时它都在钓鱼。
可是这个机器人呢，它只会钓鱼，而且它钓的鱼可能还会跳走，现在给你机器人每个小时钓鱼的成果（钓上来的鱼减去跳走的鱼的数量），
要你再给它的芯片输入一条程序，让他能够统计出来有多少次连续段（单位：小时）里面成果等于一个目标值。举个例子：
给你6个小时里面机器人钓鱼的数据：
1,2,3,1,2,4
目标值：
3
那么你写的程序能够反馈给机器人的数据是：
3
注："1,2","3","1,2"这3个连续时间段

Input

第一行n个整数（n>0&&n<=30000，每个整数绝对值不超过1000），用逗号隔开
第二行目标值target（保证答案存在）

Output

一个整数，表示有几个连续时间段满足条件

Sample Input

1,2,3,1,2,4
3

Sample Output

其实我觉得这道题的数据里是有可能是负数的，我是这么分析的：题目中说给我们的数据是机器人每个小时钓鱼的成果，并且说这个成果是钓上来的鱼减去跳走的鱼的数量，那么这时候就要注意了，因为这时候这个成果就可能是负数了，因为在单个小时内，跳走的鱼可能大于钓上来的鱼啊，比如说，

第一个小时钓了10条，跳走3条，成果是7条

第二个小时钓了5条，跳走2条，成果是3条

第三个小时钓了2条，跳走4条，成果是-2条

注意题目中给的数据是每个小时钓鱼的成果

可是我发现oj里的数据居然没有负数，是我想多了还是这题的数据不全面呢，

那就直接搜索就好了，挺简单的

以下是代码：

 1 #include<iostream>
 2 #include<vector> 
 3 using namespace std;
 4 vector<int> vec;
 5 long long num;
 6 long long sum;
 7 int target;
 8 void dfs(long long  x){
 9     if(x==vec.size()){
10         sum=0;
11         return;
12     }
13     sum+=vec[x];
14     if(sum==target){
15         num++;
16         sum=0;
17         return;
18     }
19     if(sum>target){
20         sum=0;
21         return;
22     }
23     dfs(x+1);
24 }
25 int main(){
26     char t;
27     int a;
28     scanf("%d",&a);
29     vec.push_back(a);
30     t=getchar();
31     while(t==','){
32         scanf("%d",&a);
33         if(a<0)
34             printf("hahaha"); 
35         vec.push_back(a);
36         t=getchar();
37     }
38     scanf("%d",&target);
39     long long  len=vec.size();
40     for(long long i=0;i<len;i++)
41         dfs(i);
42     printf("%lld",num);    
43     return 0;
44 }

这里我再粘下可以处理负数的搜索的方法：

 1 #include<stdio.h>
 2 int target;
 3 int vec[30005];
 4 long long num;
 5 long long sum;
 6 int m;
 7 void dfs(int x){
 8     if(x==m){//如果到了最后一个数，就结束 
 9         sum=0;
10         return;
11     }
12     sum+=vec[x];//加上这个数 
13     if(sum==target){//如果当前加和等于目标值了 
14         num++;//结果加1 
15         sum=0;
16         return;//结束 
17     }
18     dfs(x+1);//如果没结束就继续搜索 
19 }
20 int main(){
21     char t;
22     while(1){
23         scanf("%d",&vec[m++]);
24         t=getchar();
25         if(t!=',')
26             break;
27     }
28     scanf("%d",&target);
29     for(int i=0;i<m;i++)
30         dfs(i);
31     printf("%d",num);    
32     return 0;
33 }

然后说下别的比较好的做法

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 long long sum;
 5 long long num;
 6 int main(){
 7     int a;
 8     char t;
 9     int target;
10     vector<int> vec;
11     while(1){
12         scanf("%d",&a);
13         vec.push_back(a);
14         t=getchar();
15         if(t!=',')
16             break;
17     }
18     scanf("%d",&target);
19     int rear=0,front=0;
20     int len=vec.size();
21     while(rear<len||front<len){//限制条件 
22         while(sum<target&&rear<len)//可以加就加 
23             sum+=vec[rear++];
24         while(sum>target&&front<len)//可以减就减 
25             sum-=vec[front++];
26         if(sum==target){//当等于目标值时， 
27             num++;//结果加1 
28             if(rear<len)//然后在进行一次加减 
29                 sum+=vec[rear++];
30             if(front<len)    
31             sum-=vec[front++];    
32         }
33         if(rear==len&&front<len)//这个为了尽快跳出循环 
34             front++;        
35     }
36     printf("%lld",num);//输出 
37     return 0;
38 }

这个方法用的时间很少，主要的思想就是，在这一堆数里边形成一个会动的数列，我脑子里的形状是这样的

目标是要找一个目标值是吧，就是把一堆数加起来得这个目标值就行了，那我们就先加，只要和还小于目标值就一直加，一直加到大于目标值或者等于目标值，如果大于目标值的话，就来减的，减去第一个，减去第二个，一直减到小于目标值或者等于目标值，就这样循环，如果等于目标值的话，结果数就加一，这时注意，我们要加上后边的一个数，再减去后面的一个数，如果不这样做的话，下次进入循环后，和还是目标值，这样就会一直死循环了，所以要提前先进行一次操作，这样就能让和大于等于或小于了，然后当rear已经到达最后了，front还没有到最后时，此时和一定是小于等于目标值，而且还只能做减法操作，所以就不能再达到目标值了，所以让front自增只是为了能跳出循环，否则就要一直死循环了。