6609 - Minimal Subarray Length-白红宇

6609 - Minimal Subarray Length

阅读量：5744 次

发布时间：2019-06-18

本文共 1964 字，大约阅读时间需要 6 分钟。

You are given an integer sequence of length N and another value X. You have to ﬁnd a contiguous

subsequence of the given sequence such that the sum is greater or equal to X. And you have to ﬁnd

that segment with minimal length.

Input

First line of the input ﬁle contains T the number of test cases. Each test case starts with a line

containing 2 integers N (1 ≤ N ≤ 500000) and X (−109 ≤ X ≤ 109

). Next line contains N integers

denoting the elements of the sequence. These integers will be between −109

to 109

inclusive.

Output

For each test case output the minimum length of the sub array whose sum is greater or equal to X. If

there is no such array, output ‘-1’.

Sample Input

5 4

1 2 1 2 1

6 -2

-5 -6 -7 -8 -9 -10

5 3

-1 1 1 1 -1

Sample Output

-1

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            using namespace std;const int N = 510000;const int INF = 0x3fffffff;typedef long long LL;#define met(a,b) (memset(a,b,sizeof(a)))struct node{ LL x; int Start;} sum[N];LL a[N];int main(){ int T; scanf("%d", &T); while(T--) { int n, i, Min=N, X, Start; LL x; met(a, 0); met(sum, 0); scanf("%d%lld", &n, &x); for(i=1; i<=n; i++) scanf("%lld", &a[i]); for(i=1; i<=n; i++) { if(sum[i-1].x<=0 || i==1) { sum[i].x = a[i]; sum[i].Start = i; } else { sum[i].x = sum[i-1].x + a[i]; sum[i].Start = sum[i-1].Start; } if(sum[i].x>=x) { Min = min(Min, i-sum[i].Start+1); X = sum[i].x, Start = sum[i].Start; while(X>=0 && Start<=i) { X -= a[Start]; Start++; if(X >= x) { sum[i].x = X; sum[i].Start = Start; Min = min(Min, i-Start+1); } } } } printf("%d\n", Min!=N?Min:-1); } return 0;}/**3005 41 2 1 2 16 -2-5 -6 -7 -8 -9 -105 3-1 1 1 1 -18 61 1 1 1 1 2 3 46 54 -3 4 -1 2 26 6-5 1 2 4 1 36 54 -3 4 -1 -2 26 5-1 -1 -2 3 -2 54 53 -2 4 18 61 1 1 1 1 3 1 28 61 1 1 1 1 3 2 18 61 1 1 1 1 3 1 1**/

转载于:https://www.cnblogs.com/YY56/p/5473135.html

你可能感兴趣的文章