【练习】Subsequence
Subsequence
https://ac.nowcoder.com/acm/problem/107658
题目
题目描述： 给出了一个N个正整数（10 <N <100 000）的序列，每个正整数小于或等于10000，并且给出了一个正整数S（S <100 000 000）。
编写程序以查找序列中连续元素的子序列的最小长度，其总和大于或等于S。
第一行是测试用例的数量。对于每个测试用例，程序必须从第一行读取数字N和S，并以一个间隔将其隔开。
序列号在测试用例的第二行中给出，以间隔分隔。输入将以文件结尾结束。
对于每种情况，程序都必须将结果打印在输出文件的单独行上。如果没有答案，则打印0。
解析
这道题，标准的前缀和+尺取题。
先按大大说的把我们亲切的暴力方法说出来：
- 因为我们要选取子区间，所以如果要枚举的话就要枚举区间的左右端点。
- 然后我们要找区间的最小和，我们就要把区间和求出来。
- 所以枚举左端点，枚举右端点，计算区间和。暴力时间复杂度为O(n3)。
然后我们就要用更好的算法让计算更快。
前缀和：
- 我们在之前的题目讲过了很多次，前缀和就是前面的数到自己的总和。相减可以快速求出一段区间的和。
- 所以我们在这里就可以将第三层循环：计算区间和。用前缀和代替。现在时间复杂度：O(n2)。
尺取法：
- 尺取简单来说就是用一把“尺子”量取一段区间，在里面进行各种操作。操作这把“尺子”只要操作两个区间端点就行了。
- 这里用尺取的最大理由是啥呢？因为这里全部都是正数，在我们量了一段区间后。
如果这个区间是大于S的，任何一个该区间的延长区间都不用考虑了，因为一定大于S。我们这样就可以排除很多没用的枚举。 - 所以我们从头枚举左右区间，右端点移动到比S大后，就让左端点移动到比S小（在途中记录下最小值就好了）。
打代码咯：
- 先用输入初始我们的前缀和数组。
- 然后用尺取法遍历一遍数组。
- 看我代码咯~
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;
}
//函数区牛客算法竞赛入门课题解 文章被收录于专栏
憨憨的专栏
