题解：[PO Final 2022] 海滩 / Badstrand

· · 题解

题目就是要求区间和不超过 B 的最长长度。

我们可以用一个队列维护这个区间。先把这个 A_i 塞进队列里面。如果这个队列里面的和小于等于 B，那么就是可以继续扩充的。否则就要弹出队首，直到队列里面的和小于等于 B 为止。

答案就是每一次调整完队列之后队列的长度取 \max 就行了。

所以赛场上 T1 没做出来的都在干什么呢？

AC 代码：

#include <iostream>
#include <queue>
#define int long long 
using namespace std;

int a[100005];
queue<int> q;
int sum = 0;//统计区间内的和
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,b;
    int maxn = 0;
    cin>>n>>b;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    for(int i = 1;i<=n;i++){
        q.push(a[i]);
        sum+=a[i];//先加进去
        while(sum>b){//如果和超过了B
            int f = q.front();
            q.pop();
            sum-=f;//就把队首弹出
        }
        maxn = max(maxn,(int)q.size());//每次求最大值
    }
    cout<<maxn;
    return 0;
}