本文主要是介绍POJ - 3061 Subsequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：求一个有n个正整数组成的序列，给定整数S，求长度最短的连续序列，使得它们的和大于等于S
思路：第一种方法：用二分找到满足B[j]-B[i] >= S的最小的长度，复杂度O(nlogn)
第二种方法：由于j是递增的，B[j]也是递增的，所以B[i-1]<=B[j]-S的右边也是递增的，也就是说满足条件的i的位置也是递增的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100005;int A[MAXN],B[MAXN];
int n,S;int main(){int t;scanf("%d",&t);while (t--){scanf("%d%d",&n,&S);for (int i = 1; i <= n; i++)scanf("%d",&A[i]);B[0] = 0;for (int i = 1; i <= n; i++)B[i] = B[i-1] + A[i];int ans = n+1;for (int j = 1; j <= n; j++){int i = lower_bound(B,B+j,B[j]-S) - B;if (i > 0)ans = min(ans,j-i+1);}printf("%d\n",(ans == n+1) ? 0 : ans);}return 0;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100005;int A[MAXN],B[MAXN];
int n,S;int main(){int t;scanf("%d",&t);while (t--){scanf("%d%d",&n,&S);for (int i = 1; i <= n; i++)scanf("%d",&A[i]);B[0] = 0;for (int i = 1; i <= n; i++)B[i] = B[i-1] + A[i];int i = 1,ans = n+1;for (int j = 1; j <= n; j++){if (B[i-1] > B[j] - S)continue;while (B[i] <= B[j] - S)i++;ans = min(ans,j-i+1);}printf("%d\n",(ans == n+1) ? 0 : ans);}return 0;
}这篇关于POJ - 3061 Subsequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
