P8879 『STA - R1』Crossnews

· · 题解

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;
}