本题正解是尺取法

就是计算出每一时段能看到的最多的小于题目要求的羊的数量，同时比较草场的数量，最后求出答案。

那么问题就来了，如何利用较少的时间求出当前的羊的只数呢？就要利用尺取法。

首先，我们需要定义两个变量，表示当前所选择的连续草场段数，一个变量表示当前羊的只数。

int i=1,j=1,sum=0;

 

因为我们只需要求出每一段的最大值，所以不需要算出其他的羊的只数，只需要从上一个最大值演变过来就行了。

while(i<=n&&j<=n)    {        if(sum+a[j]<=t)        {            sum+=a[j];            ++j;        }        else        {            sum-=a[i];            ++i;        }        if(j-i>ans)        {            ans=j-i;            x=i;            y=j-1;        }    }

 

不要忘记在循环时储存答案。然后就可以AC了。

2018-9-25