自动搬运

查看原文

来自洛谷，原作者为

	Thunder_S 咖啡馆与广场有三个街区，就像霓虹灯到月亮的距离。

搬运于2025-08-24 22:43:21，当前版本为作者最后更新于2023-06-17 15:52:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Solution

我们考虑如何得到最优的 $\{b_n\}$。

对式子进行简单的变形：

$$\sum_{i=1}^nb_i\left(b_i-a_i\right)=\sum_{i=1}^n\left(b_i-\frac{a_i}{2}\right)^2-\sum_{i=1}^n\frac{a_i^2}{4} $$

后面那部分是定值，我们只需要最小化前面那部分即可。

令 $A_i=\frac{a_i}{2}$（方便叙述）。

先从简单情况出发。当 $n=2$ 时，如果 $A_1\le A_2$，那么 $b_1=A_1,b_2=A_2$ 即可。但如果 $A_1>A_2$，由于题目要求 $b_1\le b_2$，我们就不能同时使两个括号内部为 $0$。下面我们证明，当 $b_1=b_2=\dfrac{A_1+A_2}{2}$ 时，取得最优结果。

建立一个平面直角坐标系。注意到 $\left(b_1-A_1\right)^2+\left(b_2-A_2\right)^2$ 就表示点 $\left(b_1,b_2\right)$ 到点 $\left(A_1,A_2\right)$ 距离的平方。所以我们需要最小化这个距离。

由于 $A_1>A_2,b_1\le b_2$，所以点 $(A_1,A_2)$ 在直线 $y=x$ 的下方，点 $(b_1,b_2)$ 在直线的上方（包括直线）。根据垂线段最短可以得到，当点 $(b_1,b_2)$ 在直线 $y=x$，且同时经过 $(b_1,b_2)$ 和 $(A_1,A_2)$ 的直线与 $y=x$ 垂直时，距离最短。可以解得此时 $b_1=b_2=\dfrac{A_1+A_2}{2}$。这个证法显然可以推到多个括号。

到此，我们解决了 $n=2$ 的问题。进一步的，我们似乎得到了一种通用的解法。

总结上面的做法，现在我们需要将 $A_i$ 分成若干个区间，并且保证每个区间的平均数单调不减，并且使区间数尽量大。对于每个区间，记录 $(l,v)$ 表示该区间长度为 $l$，平均数为 $v$。对于新的元素 $(1,A_i)$，如果 $A_i$ 小于上个区间的平均数，那么就合并两个区间。最后，如果 $i$ 所在区间记为 $(l_0,v_0)$，就有 $b_i=v_0$。

Code

#include<cstdio>
#define N 1000005
#define db double
using namespace std;
int n,cnt;
db ans,a[N];
struct node 
{
    int len;
    db val;
    node (int l=0,db v=0) {len=l;val=v;}
}q[N];
node merge(node x,node y) {return node(x.len+y.len,(x.val*x.len+y.val*y.len)/(x.len+y.len));}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%lf",&a[i]);
        a[i]/=2;
    }
    for (int i=1;i<=n;++i)
    {
        q[++cnt]=node(1,a[i]);
        while (cnt>1&&q[cnt].val<q[cnt-1].val) 
            q[cnt-1]=merge(q[cnt],q[cnt-1]),cnt--;
    }
    for (int i=1,j=1;i<=cnt;++i)
        while (q[i].len--)
        {
            ans+=q[i].val*(q[i].val-a[j]*2);
            j++;
        }
    printf("%.7lf\n",ans);
    return 0;
}