挑战程序设计竞赛-day10

常用技巧

尺取法

POJ 3061：Subsequence

给定长度为n 的数列整数$a_0,a_1,…,a_{n-1} $以及整数S。求出总和不小于S 的连续子序列的长度的
最小值。如果解不存在，则输出0。

void solve() {
    memset(sum, 0 ,sizeof(sum));
    for(int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + a[i];
    }
    if(sum[n] < s) {
        printf("0\n");
        return ;
    }
    int res = n;
    for(int i = 0; sum[i] + s <= sum[n];i++) {
        int t = lower_bound(sum + i, sum + n, sum[i] + s) - sum;
        res = min(res, t - i);
    }
    printf("%d\n", res);
}

void solve() {
    int res = n + 1;
    int b = 0, t = 0, sum = 0;
    for(;;) {
        while(t < n && sum < s) {
            sum += a[t++];
        }
        if(sum < s) {
            break;
        }
        res = min(res, t - b);
        sum -= a[b++];
    }
    if(res > n) {
        res = 0;
    }
    printf("%d\n", res);
}