首页 > 代码库 > POJ3061 Subsequence
POJ3061 Subsequence
题目大意:给定长度为n的整列整数a[0],a[1],……a[n-1],以及整数S,求出总和不小于S的连续子序列的长度的最小值。
PS:用二分或者直尺法。省赛热身。
#include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <cstring> using namespace std; const int INF = 0x3fffff; vector<int> v; int n, S; int work() { int ans = INF; int l=0, r = 0; int sum = 0; for(int i = 0; i < n && sum < S; i++) { sum += v[i]; r = i; } if(sum < S) return 0; while(r < n && l <= r) { if(sum<S && r < n) { sum += v[++r]; } if(sum >= S && r<n) { ans = min(ans, r-l+1); sum = sum - v[l++]; } } return ans; } int main() { int T; //freopen("in", "r", stdin); scanf("%d", &T); int t; while(T--) { scanf("%d%d", &n, &S); v.clear(); for(int i = 0; i < n; i++) { scanf("%d", &t); v.push_back(t); } int res = work(); printf("%d\n", res); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。