Subsequence

wjh15101051's space

卧薪尝胆，厚积薄发。

Subsequence

Date: Mon Sep 17 14:01:00 CST 2018

In Category: NoCategory

Description：

给一个长为 $n$ 的序列，找一个最短的元素之和大于 $s$ 的子区间。

$1\le n \le 100000$

Solution：

对于每个 $l$ ，最小的合法的 $r$ 单调不减，于是双指针扫一遍即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

int a[MAXN];

int sum[MAXN];

void work()

{

	scanf("%d%d",&n,&m);

	int ans = 0;

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	if(m == 0)

	{

		cout << 1 << endl;

		return;

	}

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + a[i];

	for(int i = 1,j = 1;sum[n] - sum[i - 1] >= m && i <= n;++i)

	{

		while(sum[j] - sum[i - 1] < m)++j;

		if(ans == 0 || j - i + 1 < ans)ans = j - i + 1;

	}

	cout << ans << endl;

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}

In tag:

wjh15101051