算法学习:尺取法

发布于 / 算法学习 / 0 条评论

假设给你一个数组与一个整数,要求你的到这个数组中的一个子区间使其的区间和等于这个整数,你会怎么做呢。可能首先想到的就是开一个双重循环,然后每一次都求一次和,然后和给定的数进行比较:

int sum;
int ansi, ansj;
for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
        sum = 0;
        for(int k = i; k <= j; k++){
            sum += ls[k];
        }
        if(sum == x){
            ansi = i; ansj = j;
            goto ans;
        }
    }
}
ans:
printf("%d %d\n", ansi, ansj);

这样的话,复杂度就会到达 O(n^2)

尺取法的算法思想来源于以上那个算法,区别在于不再对前后指针进行疯狂枚举,也不再需要每次都进行一次求和。我们设置两个指针,起初都指向开头。然后如果区间的元素和小于给定的数,则将右指针右移。如果大于指定的数,则将区间的左指针右移。相同就出结果了。这样的话每次求和只需要加上或减去那个唯一一个有区别的元素。复杂度会降低到 O(n)

如下习题(POJ 3016):

Description

A sequence of N positive integers (10 < N < 100000), each of them less than or equal 10000, and a positive integer S(S < 100000000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

Input

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file. if no answer, print 0.

Sample Input

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

Sample Output

2
3

AC代码:

#include <cstdio>
#include <climits>
using namespace std;
int lis[100005];
long long sum;
int min(int a, int b){
    if(a > b)
        return b;
    else return a;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int N, S;
        scanf("%d %d", &N, &S);
        for (size_t i = 0; i < (size_t)N; i++) {
            scanf("%d", &lis[i]);
        }
        int left = 0, right = 0;
        sum = lis[0];
        int ans = INT_MAX;
        while(left <= right && right < N){
            if(sum < S){
                right++;
                sum += lis[right];
            }else if(sum >= S){
                ans = min(ans, right - left + 1);
                sum -= lis[left];
                left++;
            }
        }>
        if(ans != INT_MAX)
            printf("%d\n", ans);
        else printf("0\n");
    }
}
转载原创文章请注明,转载自: KONGJUNE » 算法学习:尺取法
Not Comment Found