0x01 思路：

首先想到的便是暴力+前缀和，O(n^2)
1≤n≤100000显然过不去 就想了想二分 但突然想到，这不就是一个尺取法吗？

尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案，所以要先判断是否可以使用尺取法再进行计算。

但虽然说了这么多，我还是写的二分(

对于每一个点 p ，二分最大的点 q，使p到q的和小于等于t

​

t 会不会越界？
不会，因为二分后 r = p - 1 ，r-p+1 的值为 0。

0x02 代码

尺取法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int N=1e5+10;
int a[N],n,t;

int main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int l=1,r=1,s=0,ans=0;
    while(233){
        while(r<=n&&s<=t) s+=a[r++];
        if(s<=t){
            ans=max(ans,r-l);
            break;
        }
        else ans=max(ans,r-l-1);
        s-=a[l++];
    }
    printf("%d\n",ans);
    return 0;
}
//不是本人写的AWA

普通二分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
int n,m,a[100050];
int ans=0;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		// cout<<i<<endl;
		cin>>a[i];
		a[i]+=a[i-1];
	}
	// cout<<"F"<<endl;
	for(int i=1;i<=n;i++)
	{
		int l=i,r=n;
		while(l<=r)
		{
			// cout<<"t"<<endl;
			int mid=l+r>>1;
			if(a[mid]-a[i-1]<=m)
			l=mid+1;
			else
			r=mid-1;
		}
		ans=max(ans,r-i+1);
	}
	cout<<ans<<endl;
	return 0;
}