uva 1121 - Subsequence(子序列)

本文主要是介绍uva 1121 - Subsequence(子序列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个长度为n的整数序列，要求输出大于等于s的子序列的最小长度。

思路：

  对于一个子区间（i,j），枚举j的同时来更新i，使得时间复杂度为O(n)。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>#define M 100005
#define INF 0x7fffffff
#define eps 1e-8
#define mod 100000007using namespace std;int a[M];int main ()
{int n, s;while(~scanf("%d%d", &n, &s)){for(int i = 0; i < n; ++i)scanf("%d", &a[i]);int sum = 0, i = 0, ans = n;for(int j = 0; j < n; ++j){sum += a[j];while(sum-a[i]>=s) {sum -= a[i];++i;}if(sum>=s) ans = min(ans, j-i+1);}if(sum<s) ans = 0;printf("%d\n", ans);}return 0;
}

这篇关于uva 1121 - Subsequence(子序列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---