专栏文章

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

GGeorgeDeng
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mintjwzy
此快照首次捕获于
2025/12/02 08:07
3 个月前
此快照最后确认于
2025/12/02 08:07
3 个月前
查看原文
题目就是要求区间和不超过 BB 的最长长度。
我们可以用一个队列维护这个区间。先把这个 AiA_i 塞进队列里面。如果这个队列里面的和小于等于 BB，那么就是可以继续扩充的。否则就要弹出队首，直到队列里面的和小于等于 BB 为止。
答案就是每一次调整完队列之后队列的长度取 max⁡\max 就行了。
所以赛场上 T1 没做出来的都在干什么呢？
AC 代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...