LA 2678 Subsequence

题意：给出n个整数，给定整数S,求长度最短的连续序列，使它们的和大于或等于S

第一种，是求前缀和，然后用lower_bound来找

第二种，尺取法，

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=100005;
17 
18 int n,S;
19 int a[maxn],sum[maxn];
20 
21 int main(){
22     while(scanf("%d %d",&n,&S) != EOF){
23         memset(a,0,sizeof(a));
24         memset(sum,0,sizeof(sum));
25         for(int i = 0;i < n;i++) scanf("%d",&a[i]);
26         sum[0] = a[0];
27         for(int i = 1;i < n;i++) sum[i] = sum[i-1] + a[i];
28         
29     //    for(int i =0;i <= n;i++)
30     //    printf("sum[%d] = %d
",i,sum[i]);
31         if(sum[n-1] < S){
32             printf("0
");
33         }
34         else{
35             int res = INF;
36         for(int s = 0;sum[s] + S <= sum[n-1];s++){
37             int t = lower_bound(sum,sum + n,sum[s] + S) - sum;
38             res = min(res,t-s);
39         //    printf("res = %d
",res);
40         }
41         printf("%d
",res);
42         }        
43     }
44     return 0;
45 }

View Code

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=100005;
17 
18 int a[maxn];
19 int n,S;
20 
21 void solve(){
22     int t = 0,s = 0;
23     int res = INF;
24     int sum = 0;
25     for(;;){
26         while(t < n && sum < S){
27             sum += a[t++];
28         }
29         if(sum < S) break;
30         res = min(res,t - s);
31         sum -= a[s++];
32     }
33     if(res > n) res = 0;
34     printf("%d
",res);
35 }
36 
37 int main(){
38     while(scanf("%d %d",&n,&S) != EOF){
39         memset(a,0,sizeof(a));
40         for(int i = 0;i < n;i++) scanf("%d",&a[i]);
41         solve();
42     }
43     return 0;
44 }

View Code