uva 1121 - Subsequence(TwoPointer)

题目链接: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;
}


uva 1121 - Subsequence(TwoPointer)

上一篇:FusionCharts封装-dataset和categories


下一篇:Word Break II