尺取 模板 POJ-3061

题目：

Description

Input

Output

Sample Input

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

Sample Output

2
3

题意：给定长度为n的数列，整数s。求总和不小于s的连续子序列长度最小值 。若解不存在，输出0。

方法：尺取。若下标为i~j的区间为最初的总和大于S的连续子序列，那么一定有性质：（i+1)~j 之和 < s 。

则若以下标i为起点的序列之和比s小，j就一直向后，并使序列之和加上j对应的数列元素。若j直到数列最后都没能使和大于s，则搜索结束。

当序列满足>=s的条件时，由于要保证序列长度最小，j停止移动，并检查满足条件的最小序列长度，更新。以i为起点的连续序列搜索结束。

之后由于上述性质，搜索以i+1为起点的序列时，j保持之前的位置即可。

代码：

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#define sd(x) scanf("%d",&x)
#define ss(x) scanf("%s",x)
#define sc(x) scanf("%c",&x)
#define sf(x) scanf("%f",&x)
#define slf(x) scanf("%lf",&x)
#define slld(x) scanf("%lld",&x)
#define me(x,b) memset(x,b,sizeof(x))
#define pd(d) printf("%dn",d);
#define plld(d) printf("%lldn",d);

typedef long long ll;

using namespace std;

const int INF = 0x3f3f3f3f;

int a[100010];

int main(){
	ios::sync_with_stdio(false);
	int t;
	cin>>t;	
	while(t--){
		int n,s;
		int ans = INF;
		cin>>n>>s;
		for(int i = 1 ; i<=n ; i++){
			cin>>a[i];
		}
		int i = 1,j = 1;//i为序列的首，j为序列的尾 
		int sum = 0;
		
		while(1){
			while(j<=n && sum<s){ //找到第一个末位置使序列之和大于s 
				sum+=a[j];
				j++;
			} 
			if(sum<s)	break;    //从i一直到给出数列的尾部的所有和都不能大于等于s的情况，
								  //之后的所有和只可能比当前小，退出 
			
			ans = min(ans,j-i);
			sum -= a[i];
			i++; 
		} 
		
		
		if(ans == INF){
			ans = 0;
		}
	
		cout<<ans<<endl;

	}
	return 0;
}

最后

以上就是英俊水池为你收集整理的尺取 模板 POJ-3061的全部内容，希望文章能够帮你解决尺取 模板 POJ-3061所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。