尺取法模板

天降馅饼
Description

棉帽子同学这天走在街上，突然看到前面很多钱袋，呈一字排开，每个袋面上都标有里面的钱数，棉帽子笑了，想着：不孬~

但是他也不想特别贪婪，他只想总共拿不少于S块钱，而且他要拿位置连续的钱袋(事儿事儿的)，但是他还不知道该怎么拿…

聪明的你能不能帮他算出他最少要拿多少个钱袋.

Input
输入的第一行为整数n和S(1<=n<=100000,1<=S<=1e9);第二行为n个整数，a[i]代表第i个钱袋里的钱数,(0<=a[i]<=1e9).

Output
输出他最少要拿多少个钱袋.如果不存在这样的方案,输出-1.

Sample Input 1

5 7
5 4 3 2 1
Sample Output 1

2
Sample Input 2

3 5
1 1 1
Sample Output 2

-1

#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;

int a[100009];

int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	long long ans=0;
	for(int i=1;i<=m;i++){
	scanf("%d",&a[i]);
// cout<<a[i];
	ans+=a[i];	
	}
	if(ans<n){
		printf("-1\n");
		return 0;
	}
	int l=1,r=1;
	ans=0;
	int count=0;
	int cnt=999999;
	while(r<=m){
		while(ans<n&&r<=m){
			ans+=a[r];
			r++;
			count++;
		}
		while(ans>=n){
		ans-=a[l];
		l++;
		count--;
		}
		cnt=min(cnt,count+1);
	}
	cout<<cnt<<endl; 
}
Share