POJ - 3061(总和不小于S的连续子序列的长度的最小值)

题目链接:https://vjudge.net/contest/305087#problem/C

翻译:
给出了N个正整数序列(10 < N < 100,000),每个正整数小于或等于10000,一个正整数S (S < 100,000 000)。编写一个程序,求序列中连续元素的子序列的最小长度,其和大于或等于S。
输入:
第一行是测试用例的数量。对于每个测试用例,程序都必须读取从第一行开始的数字N和S,它们之间有一个间隔。序列的编号在测试用例的第二行中给出,用间隔隔开。输入将在文件末尾结束。
输出:
对于每种情况,程序都必须在输出文件的单独行上打印结果。如果没有答案,打印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

思路:
1.设以a(s)开始总和最初大于S时的连续子序列为a(s)+…+a(t-1) //注:()内为下标值
2.可以得出:a(s+1)+…+a(t-2)<a(s)+…+a(t-2)<S
3.所以:如果a(s+1)+…+a(t’-1)总和超过S必然有t<=t’

思路转化为算法:
1.以s=t=aum=0初始化
2.只要依然有sum<S,就不断sum增加a(t),并将t增加1
3.如果(2)中无法满足sum>=S则终止。否则的话,更新res=min(res,t-s);
4.将sum减去a(s),s增加1然后回到(2)

核心代码:

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

后记:我不喜欢把完整的代码全写出来,别人的终究是别人的思路,学到知识点才是最重要的,自己一定要动手敲敲

版权声明:本文为lylzsx20172018原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lylzsx20172018/article/details/90755105