题目大意：找出一个序列中比至少和S相等的最短子序列（连续的）
本来这道题可以二分法来做复杂度O(NlogN)，也可以用一个类似于游标卡尺的方法O(N)来做
先来讲游标卡尺法：
因为子序列是连续的，所以我们只用维护这个序列的开头和结尾就行了，保证这个序列的和一定要大于S，如果从头到尾的和都没S大那就直接输出0就好，ans初始化为n+1
1 #include <iostream> 2 #include <functional> 3 #include <algorithm> 4 5 using namespace std; 6 7 static int nums[100001]; 8 9 int main(void) 10 { 11 int tests_sum, S, num_sum, lb, rb, tmp_sum, ans; 12 scanf("%d", &tests_sum); 13 14 while (tests_sum--) 15 { 16 scanf("%d%d", &num_sum, &S); 17 for (int i = 0; i < num_sum; i++) 18 scanf("%d", &nums[i]); 19 20 lb = 0; rb = 0; tmp_sum = 0; ans = num_sum + 1; 21 while (1) 22 { 23 while (rb < num_sum && tmp_sum < S) 24 tmp_sum += nums[rb++]; 25 if (tmp_sum < S) 26 break; 27 ans = min(ans, rb - lb); 28 tmp_sum -= nums[lb++]; 29 } 30 printf("%d ", ans>num_sum ? 0 : ans); 31 } 32 return 0; 33 }
二分做法：主要是对sum进行枚举，我们知道sum一定是按照下标递增的（数都是正数），那么我们只要二分枚举到一个sum[t]-sum[s]（也就是序列的值）比S刚好大就好了（lower_bound的功能）
1 #include <iostream> 2 #include <functional> 3 #include <algorithm> 4 5 using namespace std; 6 7 static int nums[100001],nums_sum_set[100001]; 8 9 int main(void) 10 { 11 int tests_sum, S, num_sum, rb, ans; 12 scanf("%d", &tests_sum); 13 while (tests_sum--) 14 { 15 scanf("%d%d", &num_sum, &S); 16 for (int i = 0; i < num_sum; i++) 17 scanf("%d", &nums[i]); 18 for (int i = 0; i < num_sum; i++) 19 nums_sum_set[i + 1] = nums_sum_set[i] + nums[i]; 20 21 if (nums_sum_set[num_sum] < S) 22 printf("0 "); 23 else 24 { 25 ans = num_sum + 1; 26 for (int i = 0; nums_sum_set[i] + S <= nums_sum_set[num_sum]; i++) 27 { 28 rb = lower_bound(nums_sum_set + i, nums_sum_set + num_sum, nums_sum_set[i] + S) - nums_sum_set;//和越小，说明偏移量越小 29 ans = min(ans, rb - i); 30 } 31 printf("%d ", ans); 32 } 33 } 34 return 0; 35 }
