P8879 『STA - R1』Crossnews 题解
Inaba_Meguru
2023-01-23 00:16:31
## 题目简述
> - 给定长度为 $n$ 的数列 $a_i$，求**实数不降**数列 $b_i$ 最小化
>
> $$
\sum_{i=1}^n b_i(b_i-a_i)
$$
>
> - $n\leq 10^6$。
## 解题思路
挺妙的题目。
我们可以先化一下式子，变成
$$
\sum_{i=1}^n (b_i-\dfrac{a_i}{2})^2-\sum_{i=1}^n \dfrac{a_i^2}{4}
$$
右边显然是定值，我们只要左边尽可能小，假设 $A_i=\dfrac{a_i}{2}$。
我们先观察一下 $n=2$ 的情况，有两种情况：
- $A_1<A_2$ 那么取 $b_i=A_i$ 即可。
- 否则应该取 $b_i=\dfrac{A_1+A_2}{2}$。
也许我们可以观察到这样的情况，其实每个 $b_i$ 最理想的取值是 $A_i$，但是为了要满足单调不减的性质取不到 $A_i$。这个时候就应该和他的邻居一个取值。那么这个时候他的邻居也会受到影响，原来是可以取到 $A_i$ 的因为邻居的偏袒不得不取一个其他值使得总和最小。
我们不难发现，当我们要一段**极长**连续区间 $b[l,r]$ 取一个相等的数 $x$ 的时候，这个时候必然有：
$$
x=\dfrac{1}{r-l+1}\sum_{i=l}^r A_i
$$
> **证明：** 不难发现原式相当于 $\sum(x-A_i)=(r-l+1) x^2-2(r-l+1) \overline A x+C$，这里 $C$ 为常数，不难发现当 $x$ 取 $\overline A$ 时最小。
那有没有可能这个求出 $x$ 不满足不降呢？实际上如果不满足，也就是说 $x$ 取极大极小值的时候原式更小，那么这个时候，他就会和邻居一个数值，不满足极长。
我们最后只需要求出来这个 $b$ 即可。
考虑单调栈维护，每个位置维护一个极长区间的长度、数值 $len,x$，每次先进入一个 $(1,A_i)$ 如果当前栈末尾不满足单调的性质就不断向前一位合并，直到单调或只有一个元素位置。
至此我们就完成了这道题。
## 参考代码
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1e6+5;
int n;
double a[MAXN],ans;
struct node{
int len;double val;
node (int le=0,double va=0){len=le,val=va;}
}st[MAXN];int cnt=0;
node merge(node x,node y){
return node(x.len+y.len,(x.len*x.val+y.len*y.val)/(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++){
st[++cnt]=node(1,a[i]);
while(cnt>1&&st[cnt].val<st[cnt-1].val)
st[cnt-1]=merge(st[cnt],st[cnt-1]),--cnt;
}
int l=0;
for(int i=1;i<=cnt;i++)
while(st[i].len--){
++l;
ans+=(st[i].val*(st[i].val-2*a[l]));
}
printf("%.9f",ans);
return 0;
}
```