羊羊吃草

題目連結:

    https://begin.lydsy.com/JudgeOnline/problem.php?id=3263

Description:

    小羊們上完課後，紛紛到草場上吃草。而羊村現在正在進行特色示範羊村檢查，上司們想看看羊村的草場。羊村的

 草場是連續分布的，每塊草場上都有數量不等的羊在吃草。上司們想要檢視連續若幹個草場，但是又不想看到超過

 T隻羊。而村長希望上司們多看看羊村的風貌，盡可能多參觀幾個草場。現在，請你幫村長決定，帶上司們去參觀

 哪一段草場，滿足上司和村長的要求。

Sample Input

5 10

6 3 2 1 7

Sample Output

   2 4

   2和4，可以參觀3個草場,共6隻羊.

解題思路:

    本題的本質為權值不超過t的最長連續序列. 

代碼:

#include<bits/stdc++.h>
using namespace std;
long long n,t,k,ans,a[100002],cnt,x,y;
int main(){
	scanf("%lld%lld",&n,&t);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		ans+=a[i];//起點到目前羊數 
		while(ans>t)
			ans-=a[++cnt];//如果超過,起點後移 
		if(i-cnt>y-x) 
			x=cnt,y=i;//找到更優解更新 
	}
	printf("%lld %lld\n",x+1,y);
}