专栏文章

题解：P10579 [蓝桥杯 2024 国 A] 最长子段

DDeepSleep_Zzz
P10579题解参与者 6已保存评论 9

文章操作

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

当前评论
9 条
当前快照
1 份
快照标识符
@miqkqekg
此快照首次捕获于
2025/12/04 06:23
3 个月前
此快照最后确认于
2025/12/04 06:23
3 个月前
查看原文
begin
P10579 [蓝桥杯 2024 国 A] 最长子段

Part 0 前置芝士

前缀和，二分。

Part 1 题目分析

题意已经清晰了，无需多言。
这题一个最明显也是最好想的思路就是暴力，但是显然时间复杂的是 O(n2)O(n^2) 的。而 nn 的最大值可以达到 3×1053 \times 10^5，所以这样必 TLE，但是你拿到 60 pts 后可以去借鉴别人代码了。
我们思考一下比 O(n2)O(n^2) 耗时更少的复杂度，最终我们锁定了 O(n)O(n)、O(nlog⁡n)O(n \log n) 和 O(nn)O(n \sqrt{n}) 三种时间复杂度。
经过简单的思考深思熟虑过后，我们发现，这题用 O(n)O(n) 来求解可能不太现实（或者可能是我太弱了 /bei），而 O(nn)O(n \sqrt{n}) 的耗时也有些极限，所以我们考虑 O(nlog⁡n)O(n \log n)。
再思考一下，由于 log⁡\log 出现的场合比较有限，常见的就两种，一种是排序，另一种就是二分。
很显然，这题跟排序连一分钱关系都没有，所以我们最终锁定二分。

Part 2 解题思路

二分最重要的就是单调性，没有一个单调性的数组这一切就全都是空谈。所以我们现在的问题就是如何构建一个与题目有关的且具有单调性的数组呢？
我们将目光放在题目所给的那一大段条件上（以下我们记 sumisum_i 为 s1∼sis_1 \sim s_i 的和）：
∑i=LR>a⋅(b⋅R−c⋅L)sumR−sumL−1>a⋅b⋅R−a⋅c⋅LsumR−a⋅b⋅R>sumL−1−a⋅c⋅L\begin{aligned} \sum_{i=L}^R&>a \cdot (b \cdot R-c \cdot L)\\ sum_R-sum_{L-1}&>a \cdot b \cdot R-a \cdot c \cdot L\\ sum_R-a \cdot b \cdot R&>sum_{L-1}-a \cdot c \cdot L \end{aligned}
我们考虑用一个数组 ff 存储左端点（LL），然后为了保证其单调性和正确性，我们得出数组 ff 的递推式为：
fi=min⁡(fi−1,sumi−1−a×c×i)f_i=\min(f_{i-1},sum_{i-1}-a \times c \times i)
为什么要取 min⁡\min 呢？
当 fi−1<sumi−1−a×c×if_{i-1}<sum_{i-1}-a \times c \times i 时，我们来讨论一下：
  • 如果 fi=fi−1f_i=f_{i-1}，它对答案的贡献就是： R−(i−1)+1=R−i+2R-(i-1)+1=R-i+2
  • 如果 fi=sumi−1−a×c×if_i=sum_{i-1}-a \times c \times i，它对答案的贡献是： R−i+1R-i+1 显然前者更优，足足比后者大了 11 呢！
这也同时保证了 ff 数组的单调不增的性质，为接下来的二分做好了准备。

Part 3 Tips

到了这里，这道题你就已经完成 90% 了。但是正所谓行百里者半九十，所以最后的写代码环节也是至关重要的。如果你搞不定细节，那一样完蛋。
大前提：
  • 我用的二分方法是 while (l+1<r)，如果你的方法和我不同的话可以参考一下思路。
  • 以下我们设 sumR−a⋅b⋅R=xsum_R-a \cdot b \cdot R=x。

Part 3.1

首先需要注意的就是二分时 ll 的初始值（这个跟上面的 LL 没关系！）究竟是 11 还是 00？
我们来举个栗子：若 ∀f1∼i<x\forall f_{1 \sim i} < x，当 l=1l=1 时，r=2r=2；l=0l=0时，r=1r=1。
显然 r=1r=1 是正确结果。所以 ll 的初始值为 00。

Part 3.2

然后就是每个二分的易错点：内部判断条件是 if (f[mid]<=x) r=mid 还是 if (f[mid]<x) r=mid？
要找到这个问题的答案，我们首先要知道我们的目标是找到 ff 数组的第一个 ii 使 fi<xf_i<x，所以在 fmid=xf_{mid}=x 的时候我们要继续找更小的 fmidf_{mid}，也就是找更大的 midmid，也就是右移左端点，也就是 l=midl=mid。
所以后者是正确的。

Part 4 Code

CPP
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,a,b,c,sum[300010],now,f[300010],x,l,r,mid,pos,ans;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // 输入输出加速     
    cin>>n>>a>>b>>c;
    for (ll i=1;i<=n;i++)
    {
        cin>>now; // 省点空间
        sum[i]=sum[i-1]+now; // 前缀和
    }
    f[0]=1e18; // 是极大值就行，防止第一次 min 出祸
    for (ll i=1;i<=n;i++)
    {
        f[i]=min(f[i-1],sum[i-1]-a*c*i); // 求 f 数组
        x=sum[i]-a*b*i; // x
        l=0,r=i+1;
        while (l+1<r)
        {
            mid=(l+r)>>1;
            if (f[mid]<x)
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
        }
        if (i>=r)
        {
            ans=max(ans,i-r+1); // 维护最大答案
        }
    }
    cout<<ans;
    return 0; // 完结撒花~
}
end

评论

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

正在加载评论...