解題區/解題區 - UVa

UVa 12697 - Minimal Subarray Length

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

You are given an integer sequence of length N and another value X. You have to find a contiguous subsequence of the given sequence such that the sum is greater or equal to
X. And you have to find that segment with minimal length.

Sample Input

1
2
3
4
5
6
7
3
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
2
3
3
-1
3

Solution

題目描述：

找一段長度最小，且該區間總和大於等於指定 X。

題目解法：

離散化後，利用掃描線的思路進行維護。

利用前綴和 SUM[i]，查找小於等於 SUM[i] - X 的最大值。

隨後更新 SUM[i] 位置的值 i。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
#define MAXN 5024288
#define INF 0x3f3f3f3f
long long A[MAXN], SM[MAXN], SB[MAXN];
// binary index tree
int BIT[MAXN<<1];
void modify(int x, int v, int L) {
    while(x <= L) {
        BIT[x] = max(BIT[x], v);
        x += x&(-x);
    }
}
int query(int x) {
    int ret = - INF;
    while(x) {
        ret = max(ret, BIT[x]);
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int testcase, N, X;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &N, &X);
        for(int i = 1; i <= N; i++)
            scanf("%lld", A+i);
        
        for(int i = 1; i <= N; i++)
            SM[i] = SM[i-1] + A[i];
        for(int i = 0; i <= N; i++)
            SB[i] = SM[i];
        for(int i = 1; i <= N + 1; i++)
            BIT[i] = - INF;
        sort(SB, SB + N + 1);
        int M = unique(SB, SB + N + 1) - SB;		
        int ret = INF;
        for(int i = 0; i <= N; i++) {
            long long v = SM[i] - X;
            int pos = upper_bound(SB, SB + M, v) - SB;
            if(pos - 1 >= 0 && i)  {
                ret = min(ret, i - query(pos));
//				printf("query %d\n", i - query(pos));
            }
            pos = upper_bound(SB, SB + M, SM[i]) - SB;
            modify(pos, i, M);
//			printf("%lld %d\n", v, pos);
        }
        
        printf("%d\n", ret == INF ? -1 : ret);
    }
    return 0;
}
/*
3
5 4
1 2 1 2 1
6 -2
-5 -6 -7 -8 -9 -10
5 3
-1 1 1 1 -1
*/