ARC123D Inc, Dec - Decomposition

给出长为 $n$ 的序列 $A$，构造长为 $n$ 的序列 $B,C$，要求：

• $B$ 非严格递增。
• $C$ 非严格递减。
• $B_i+C_i=A_i$ 。

最小化 ${\sum }_{i=1}^n|B_i|+|C_i|$。

这里有一个贪心：若 $A_i>A_{i+1}$，则 $B_{i+1}=B_i,C_{i+1}=C_i+A_{i+1}?A_i$，反之同理。

证明考虑反证，任取最优的 $B_{i+1},C_{i+1}(B_{i+1}>B_i,C_{i+1}<C_i)$，那么令 $B_{i+1}\leftarrow B_{i+1}?1,C_{i+1}\leftarrow C_i+1$，最后的答案不会更劣（证明可以手模一下），不停操作下去，最终可以得到结论。

那么，只要确定 $B_1,C_1$，$B_i,C_i(i>1)$ 就可以分别用 $B_1,C_1$，从而得到答案。此时把 $C_1$ 用 $A_1?B_1$ 表示，要最小化的式子就是形如 $\sum |B_1?p_i|$，最小值在 $p$ 的中位数取得。方法很多。

时间复杂度 $O(n\log n)$，这是排序的时间复杂度，可以不用排序。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
long long n,a[N],b[N],c[N],d[N];
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    c[1]=a[1];
    for(int i=2;i<=n;i++){
        if(a[i-1]>a[i]){
            b[i]=b[i-1];
            c[i]=c[i-1]+a[i]-a[i-1];
        }
        else{
            b[i]=b[i-1]+a[i]-a[i-1];
            c[i]=c[i-1];
        }
    }
    for(int i=1;i<=n;i++) b[i]=-b[i],d[i]=b[i],d[i+n]=c[i];
    sort(d+1,d+1+n*2);
    long long ans=0;
    for(int i=1;i<=2*n;i++){
        ans+=abs(d[n]-d[i]);
    }
    cout<<ans;
}