P8049 题解

Dream__Sky · 2023-09-10 23:40:25 · 题解

本题弱化版

弱化版可用二分答案的算法来求解，但是这题的数据就不支持 O(n\log n) 的解法了。

考虑尺取法。

以下定义 mid 为当前区间的中点下标，l 为左端点下标，r 为右端点下标。

普通暴力为，从 1 到 n 枚举中点 mid。从当前的 mid 开始，向左枚举，直到和大于 s，求出 l。再向右枚举，直到和大于 s，求出 r。求出 l 和 r 之后，我们可以计算以 mid 作为中点时的最大长度 K，即 K=\min(mid-l+1,r-mid)。但是题目要求的是作为开头时的最小值，那我们可以把它整体向左移 k 位，开头下标变成 mid-K+1，将这个长度记录到这一位。时间复杂度 O(n^2)。

最后，可能有一些点还没有被更新答案，那我们考虑当前这一位与前一位的关系。考虑不取前一位，为了还满足是 2 \times K 个元素，还得去掉最后一个。即前一位的最大长度减二。此时，该区间一定满足两边的和都小于 s，因为上次的区间都小于 s 了，去掉两个数后和甚至都小于原值了，所以满足条件。

如何从暴力上优化？这就要提到尺取法了。当我们变动 mid 后，l 与 r 一定都会向右移动（或者不动），那我们每次可以直接从上一次的 l 与 r 继续向右枚举，直到和大于 s。其它都与的与上面相同。时间复杂度 O(n)。

在尺取过程中，可以使用前缀和来快速计算区间和。当然也可以边尺取，边计算连续一段区间的和。

代码：

#include <bits/stdc++.h>
#define int long long 
using namespace std;
int n,s,a[100010],t[100010],c[100010];
signed main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>a[i],c[i]=c[i-1]+a[i];//前缀和

    int l=1,r=1;

    for(int i=1;i<=n;i++)//i即为mid
    {
        while(c[i]-c[l-1]>s) l++;//左端点移动
        while(c[r+1]-c[i]<=s&&r<n) r++;//右端点移动
        int K=min(i-l+1,r-i);//计算K
        t[i-K+1]=K*2;//记录长度
    } 
    for(int i=1;i<=n;i++) t[i]=max(t[i-1]-2,t[i]);//记录未被记录长度的点的长度（有点绕？
    for(int i=1;i<=n;i++) cout<<t[i]<<"\n";
    return 0;
}