Lightning Conductort题解

· · 题解

考虑N^2大暴力 ans[i]=max(a[j]+sqrt(|i-j|)-a[i] (1<=j<=n)

把绝对值拆开：

ans[i]=max(a[j]+sqrt(i-j))-a[i] (1<=j<=i)

ans[i]=max(a[j]+sqrt(j-i))-a[i] (i<j<=n)

上面两个式子显然比较对称，我们可以考虑先正着做一遍再倒着做一遍

打表课证明对于f[i]的最优决策点g[i]是单调递增的，分治即可

solve(l,r,L,R)表示f[l]~f[r]的最优决策点在L~R

令mid=（l+r）/2,O（n）扫一遍取到g[mid]

继续分治

solve（l,mid-1,L,g[mid])

solve (mid+1,r,g[mid],R)

代码如下:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
long double f1[6000000],f2[6000000];
long long a[6000000];
long long read()
{
    long long ret(0);
    char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9')
    {
        ret=(ret<<1)+(ret<<3)+ch-48;
        ch=getchar();
    }
    return ret;
}
void solve1(int L,int R,int l,int r)
{
    if (L>R) return;
    int mid=(L+R)>>1,g(0);
    long double tmp(0);
    f1[mid]=a[mid];
    for (int i=l;i<=min(r,mid);i++)
    {
        tmp=a[i]+sqrt(double(mid-i));
        if (tmp>f1[mid]) f1[mid]=tmp,g=i;
    }
    if (g==0) g=mid; f1[mid]-=a[mid];
    solve1(L,mid-1,l,g); 
    solve1(mid+1,R,g,r);
}
void solve2(int L,int R,int l,int r)
{
    if (L>R) return ;
    int mid=(L+R)>>1,g(0);
    long double tmp(0);
    f2[mid]=a[mid];
    for (int i=r;i>=max(mid,l);i--)
    {
        tmp=a[i]+sqrt(double(i-mid));
        if (tmp>f2[mid]) f2[mid]=tmp,g=i;
    }
    if (g==0) g=mid; f2[mid]-=a[mid];
    solve2(L,mid-1,l,g);
    solve2(mid+1,R,g,r);
}
int main()
{
    int n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    solve1(1,n,1,n);
    solve2(1,n,1,n);
    for (int i=1;i<=n;i++)
    printf("%lld \n",(long long)ceil(max(f1[i],f2[i])));
    return 0;
}