学步园

题目链接：uva 1121 - Subsequence

题目大意：给出一个序列，要求求出序列中最短子序列的元素和不小于k的长度。

解题思路：r维护加入，l维护减除，r - l即为当前个数。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 100005;
int n, k, num[N];

void init() {
	for (int i = 0; i < n; i++) scanf("%d", &num[i]);
}

int solve() {
	int ans = n + 1, sum = 0;
	int l = 0, r = 0;
	while (r < n) {
		sum += num[r++];
		while (sum >= k) {
			ans = min(ans, r - l);
			sum -= num[l++];
		}
	}
	return ans == n + 1 ? 0 : ans;
}

int main() {
	while (scanf("%d%d", &n, &k) == 2) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}