【挑战程序设计竞赛】 尺取法

发表于

Subsequence POJ No.3061

给定长度为 n 的数列整数 a[0], a[1], a[2],…,a[n-1],以及整数 S。求出总和不小于 S 的连续子序列的最小值。

样例

1
2
输入: n = 10,S = 15,a = {5,1,3,5,10,7,4,2,8};
输出: 2 (5+10)

思路
思路1：累加得到序列b[n],其中b[i] = a[0]+a[1]+…+a[i],i>=0,再利用二分搜索从 i 到 n-1 查找第一个大于 S 的值。
思路2：像虫子一样向前挪动。

notes: lower_bound(b+i,b+n, S + b[i]) 返回的是地址，减去 b 的首地址，即得到下标

1
2
3
4
5
6
7
8
9
10
11
12
13
int solve(int a[], int n,int S) {
    int b[100] = {0};
    for (int i = 0; i < n; i++) {
        b[i + 1] = a[i] + b[i];
    }
    if (b[n] < S) { return -1; }
    int res = n;
    for (int i = 0; b[n] - b[i] >= S; i++) {
        int t = lower_bound(b+i,b+n, S + b[i]) - b;
        res = min(res, t-i);
    }
    return res;
}

尺取法

1
2
3
4
5
6
7
8
9
10
11
12
13
int solve3(int a[], int n, int S) {
    int s = 0, t = 0, sum = 0, res = n + 1;
    for (;;) {
        while (sum < S && t < n) {
            sum += a[t++];
        }
        if (sum < S) { break; }
        res = res < t - s  ? res : t - s ;
        sum -= a[s++];
    }
    if (res <= n) { return res; }
    return -1;
}