cjb-poi2011lightningconductor

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define N 500010
double f[N],g[N];
int n;
int a[N];
void work(int l,int r,int fl,int fr,double* f)
{
    if (l>r)return;
    int mid=(l+r)/2,p=fl;
    f[mid]=0;
    for(int i=fl;i<=fr;i++)
    {
        if (i>mid)break;
        double t=a[i]-a[mid]+sqrt(mid-i);
        if (t>=f[mid])f[mid]=t,p=i;
    }
    work(l,mid-1,fl,p,f);
    work(mid+1,r,p,fr,f);
}
int main()
{
    cin>>n;
    rep(i,n)scanf("%d",&a[i]);
    work(1,n,1,n,f);
    reverse(a+1,a+n+1);
    work(1,n,1,n,g);
    rep(i,n)printf("%d\n",(int)ceil(max(f[i],g[n-i+1])));
    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define N 500010
double f[N],g[N];
int n;
int a[N];
void work(int l,int r,int fl,int fr,double* f)
{
    if (l>r)return;
    int mid=(l+r)/2,p=fl;
    f[mid]=0;
    for(int i=fl;i<=fr;i++)
    {
        if (i>mid)break;
        double t=a[i]-a[mid]+sqrt(mid-i);
        if (t>=f[mid])f[mid]=t,p=i;
    }
    work(l,mid-1,fl,p,f);
    work(mid+1,r,p,fr,f);
}
int main()
{
    cin>>n;
    rep(i,n)scanf("%d",&a[i]);
    work(1,n,1,n,f);
    reverse(a+1,a+n+1);
    work(1,n,1,n,g);
    rep(i,n)printf("%d\n",(int)ceil(max(f[i],g[n-i+1])));
    return 0;
}