题目

题目描述：
给出了一个N个正整数（10 <N <100 000）的序列，每个正整数小于或等于10000，并且给出了一个正整数S（S <100 000 000）。
编写程序以查找序列中连续元素的子序列的最小长度，其总和大于或等于S。

输入描述：
第一行是测试用例的数量。对于每个测试用例，程序必须从第一行读取数字N和S，并以一个间隔将其隔开。
序列号在测试用例的第二行中给出，以间隔分隔。输入将以文件结尾结束。

输出描述：
对于每种情况，程序都必须将结果打印在输出文件的单独行上。如果没有答案，则打印0。

解析

这道题，标准的前缀和+尺取题。

先按大大说的把我们亲切的暴力方法说出来：
  1. 因为我们要选取子区间，所以如果要枚举的话就要枚举区间的左右端点。
  2. 然后我们要找区间的最小和，我们就要把区间和求出来。
  3. 所以枚举左端点，枚举右端点，计算区间和。暴力时间复杂度为O(n3)。

然后我们就要用更好的算法让计算更快。

前缀和：
  • 我们在之前的题目讲过了很多次，前缀和就是前面的数到自己的总和。相减可以快速求出一段区间的和。
  • 所以我们在这里就可以将第三层循环：计算区间和。用前缀和代替。现在时间复杂度：O(n2)。

尺取法：
  1. 尺取简单来说就是用一把“尺子”量取一段区间，在里面进行各种操作。操作这把“尺子”只要操作两个区间端点就行了。
  2. 这里用尺取的最大理由是啥呢？因为这里全部都是正数，在我们量了一段区间后。
    如果这个区间是大于S的，任何一个该区间的延长区间都不用考虑了，因为一定大于S。我们这样就可以排除很多没用的枚举。
  3. 所以我们从头枚举左右区间，右端点移动到比S大后，就让左端点移动到比S小（在途中记录下最小值就好了）。

打代码咯：
  1. 先用输入初始我们的前缀和数组。
  2. 然后用尺取法遍历一遍数组。
  3. 看我代码咯~

AC代码 

#include <iostream> 
#include <algorithm>
using namespace std; 
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
//代码预处理区 

const int INF = 0x3f3f3f3f;
const int MAX = 1e5 + 7; 
int N, S, sum[MAX];
//全局变量区 

int main() { 
    IOS;
    int T; cin >> T;
    while (T--) {
        cin >> N >> S;
        for (int i = 1; i <= N; i++) {
            cin >> sum[i];
            sum[i] += sum[i - 1];
        }
        int l = 1, r = 1, mn = INF;
        while (r <= N) {
            if (sum[r] - sum[l] < S) {
                r++;
            }
            else {
                while (sum[r] - sum[l] >= S)
                    l++;
                mn = min(mn, r - l + 1);
            }
        }
        cout << (INF == mn ? 0 : mn) << endl;
    }
    return 0; 
}
//函数区