POJ - 3061 Subsequence（最短子序列和大于等于某值的序列长度）

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<queue>
 5 #include<algorithm>
 6 #include<time.h>
 7 #include<stack>
 8 using namespace std;
 9 #define N 1200000
10 #define INF 0x3f3f3f3f
11 
12 int dp[N];
13 int a[N];
14 
15 int main()
16 {
17     int n,m,T,i;
18 
19     scanf("%d", &T);
20 
21     while(T--)
22     {
23         scanf("%d %d", &n, &m);
24         memset(dp,0,sizeof(dp));
25 
26         for(i=1;i<=n;i++)
27         {
28             scanf("%d", &a[i]);
29             dp[i]=dp[i-1]+a[i];
30         }
31 
32         int minn=INF;
33         for(i=1;i<=n;i++)
34             if(dp[n]-dp[i-1]>=m)
35             {
36                 int ans=lower_bound(dp,dp+n,dp[i-1]+m)-dp;///二分函数
37                 minn=min(ans-i+1,minn);
38             }
39 
40       if(minn==INF)
41         printf("0\n");
42       else
43         printf("%d\n", minn);
44     }
45     return 0;
46 }