题解--P8424 [JOI Open 2022] 跷跷板（Seesaw）

· · 题解

首先，我们可以发现无论如何操作，箱子一定包含初始的 \dfrac{\sum A_i}{n} 这个位置，我们记其为 mid。于是我们考虑所有操作使箱子左端点相对 mid 向左偏移了多少，使其右端点相对 mid 向右偏移了多少。

考虑 i 次操作后的情形，我们现在还剩一个长度为 n-i 的区间 [l,r]。我们考虑重心在 mid 左边的区间重心最靠右的区间 [l_1,r_1] 和重心在 mid 右边的区间重心最靠左的区间 [l_2,r_2]。可以发现 l_2=l_1+1,r_2=r_1+1，否则我们把 [l_1,r_1] 往右平移一格或把 [l_2,r_2] 往左平移一格可以得到更优的答案。

我们需要先求出第 i 次操作后的 [l_1,r_1]，可以发现，能从第 i-1 次操作后的 [l_1,r_1] 转移过来。因为在第 i-1 次操作后的 [l_1,r_1-1] 一定在 mid 以左，[l_2+1,r_2] 一定在 mid 以右。维护两个指针即可。

容易发现，我们每一步一定取这两个区间之一，否则往 mid 方向动一定能取到并且更优。

考虑答案为最大的选取 [l_2,r_2] 的 r_2-mid 加上最大的选取 [l_1,r_1] 的 mid-l_1，于是我们枚举这个最大的 mid-l_1，相当于在这个 l_1 处划了一条红线，任何重心不能往左越过这条红线，设其为 l_*。答案的另一半贡献很明显至少取到 l_1 在这条红线以左的区间中最大的 r_2-mid，设这个 r_2 为 r_*。

我们接下来说明答案能取到。考虑这个移动的过程，如果当前我们位于 [l_1,r_1]，如果 [l_1',r_l'] 合法，我们就往这个方向走，因为 l_1'\ge l_*，所以不影响答案。否则 [l_1',r_l'] 一定相对 [l_1,r_1] 往左，所以 [l_1',r_l']=[l,r-1]，于是我们可以往 [l_2',r_2'] 走，因为这一步的 [l_1',r_1'] 不合法，所以 r_2'\le r_*，不影响答案。当位于 [l_2,r_2] 的时候同理。

于是，我们只需要按照 mid-l_1 排序，然后另一半的贡献求一个后缀 \max 就可以了。时间复杂度 O(n\log n)。 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
namespace tokidosaya {
#define fi first
#define sc second
    typedef pair<double,double> pi;
    const int maxn=2e5+5;
    int n,a[maxn];
    ll s[maxn];
    pi p[maxn];
    int main() {
        n=read();
        for(int i=1; i<=n; i++)a[i]=read(),s[i]=s[i-1]+a[i];
        double mid=1.0*s[n]/n;
        int l=1,r=n;
        for(int i=1; i<n; i++) {
            l++;
            if(1.0*(s[r]-s[l-1])/(r-l+1)>mid)l--,r--;
            p[i]=pi(mid-1.0*(s[r]-s[l-1])/(r-l+1),1.0*(s[r+1]-s[l])/(r-l+1)-mid);
        }
        sort(p+1,p+n);
        double ans=1e9,suf=0;
        for(int i=n-1; i; i--)ans=min(ans,p[i].fi+suf),suf=max(suf,p[i].sc);
        printf("%.10lf",ans);
        return 0;
    }
}
int main() {
    return tokidosaya::main();
}