尺取法模板

模板"/>

尺取法模板

天降馅饼
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