| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 9236 | Accepted: 3701 |
Description
Input
Output
Sample Input
2 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5
Sample Output
2 3
二分代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #include <map> 10 #include <queue> 11 #include <stack> 12 #include <sstream> 13 #include <iomanip> 14 using namespace std; 15 const int INF=0x4fffffff; 16 const int EXP=1e-6; 17 const int MS=100005; 18 19 int a[MS]; 20 int sum[MS]; 21 int N,S; 22 23 int main() 24 { 25 int T; 26 scanf("%d",&T); 27 while(T--) 28 { 29 scanf("%d%d",&N,&S); 30 sum[0]=0; 31 a[0]=0; 32 for(int i=1;i<=N;i++) 33 { 34 scanf("%d",&a[i]); 35 sum[i]=a[i]+sum[i-1]; 36 } 37 if(sum[N]<S) 38 { 39 printf("0\n"); 40 continue; 41 } 42 int ans=N; 43 for(int i=1;sum[i-1]+S<=sum[N];i++) 44 { 45 int index=lower_bound(sum+i,sum+N,sum[i-1]+S)-sum; 46 ans=min(ans,index-i+1); 47 } 48 printf("%d\n",ans); 49 } 50 return 0; 51 }
尺取大法好啊
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #include <map> 10 #include <queue> 11 #include <stack> 12 #include <sstream> 13 #include <iomanip> 14 using namespace std; 15 const int INF=0x4fffffff; 16 const int EXP=1e-6; 17 const int MS=100005; 18 19 int a[MS]; 20 int N,S; 21 22 int main() 23 { 24 int T; 25 scanf("%d",&T); 26 while(T--) 27 { 28 scanf("%d%d",&N,&S); 29 for(int i=0;i<N;i++) 30 scanf("%d",&a[i]); 31 int sum=0; 32 int s=0,t=0; 33 int ans=N+1; 34 while(1) 35 { 36 while(t<N&&sum<S) 37 sum+=a[t++]; 38 if(sum<S) 39 break; 40 ans=min(ans,t-s); 41 sum-=a[s++]; 42 } 43 if(ans>N) 44 printf("0\n"); 45 else 46 printf("%d\n",ans); 47 } 48 return 0; 49 }
Subsequence poj 3061 二分（nlog n）或尺取法(n)
原文：http://www.cnblogs.com/767355675hutaishi/p/4376062.html