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

· · 题解

begin

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

Part 0 前置芝士

前缀和，二分。

Part 1 题目分析

题意已经清晰了，无需多言。

这题一个最明显也是最好想的思路就是暴力，但是显然时间复杂的是 O(n^2) 的。而 n 的最大值可以达到 3 \times 10^5，所以这样必 TLE，但是你拿到 60 pts 后可以去借鉴别人代码了。

我们思考一下比 O(n^2) 耗时更少的复杂度，最终我们锁定了 O(n)、O(n \log n) 和 O(n \sqrt{n}) 三种时间复杂度。

经过简单的思考深思熟虑过后，我们发现，这题用 O(n) 来求解可能不太现实（或者可能是我太弱了 /bei），而 O(n \sqrt{n}) 的耗时也有些极限，所以我们考虑 O(n \log n)。

再思考一下，由于 \log 出现的场合比较有限，常见的就两种，一种是排序，另一种就是二分。

很显然，这题跟排序连一分钱关系都没有，所以我们最终锁定二分。

Part 2 解题思路

二分最重要的就是单调性，没有一个单调性的数组这一切就全都是空谈。所以我们现在的问题就是如何构建一个与题目有关的且具有单调性的数组呢？

我们将目光放在题目所给的那一大段条件上（以下我们记 sum_i 为 s_1 \sim s_i 的和）：

\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}

我们考虑用一个数组 f 存储左端点（L），然后为了保证其单调性和正确性，我们得出数组 f 的递推式为：

f_i=\min(f_{i-1},sum_{i-1}-a \times c \times i)

为什么要取 \min 呢？
当 f_{i-1}<sum_{i-1}-a \times c \times i 时，我们来讨论一下：

这也同时保证了 f 数组的单调不增的性质，为接下来的二分做好了准备。

Part 3 Tips

到了这里，这道题你就已经完成 90% 了。但是正所谓行百里者半九十，所以最后的写代码环节也是至关重要的。如果你搞不定细节，那一样完蛋。

大前提：

Part 3.1

首先需要注意的就是二分时 l 的初始值（这个跟上面的 L 没关系！）究竟是 1 还是 0？

我们来举个栗子：若 \forall f_{1 \sim i} < x，当 l=1 时，r=2；l=0时，r=1。

显然 r=1 是正确结果。所以 l 的初始值为 0。

Part 3.2

然后就是每个二分的易错点：内部判断条件是 if (f[mid]<=x) r=mid 还是 if (f[mid]<x) r=mid？

要找到这个问题的答案，我们首先要知道我们的目标是找到 f 数组的第一个 i 使 f_i<x，所以在 f_{mid}=x 的时候我们要继续找更小的 f_{mid}，也就是找更大的 mid，也就是右移左端点，也就是 l=mid。

所以后者是正确的。

Part 4 Code

#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