ARC123D Inc, Dec - Decomposition

2023-12-13 05:16:25

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

  • B B B 非严格递增。
  • C C C 非严格递减。
  • B i + C i = A i B_i+C_i=A_i Bi?+Ci?=Ai?

最小化 ∑ i = 1 n ∣ B i ∣ + ∣ C i ∣ \sum_{i=1}^n |B_i|+|C_i| i=1n?Bi?+Ci?


这里有一个贪心:若 A i > A i + 1 A_i>A_{i+1} Ai?>Ai+1?,则 B i + 1 = B i , C i + 1 = C i + A i + 1 ? A i B_{i+1}=B_i,C_{i+1}=C_i+A_{i+1}-A_i Bi+1?=Bi?,Ci+1?=Ci?+Ai+1??Ai?,反之同理。

证明考虑反证,任取最优的 B i + 1 , C i + 1 ( B i + 1 > B i , C i + 1 < C i ) B_{i+1},C_{i+1}(B_{i+1}>B_{i},C_{i+1}<C_i) Bi+1?,Ci+1?(Bi+1?>Bi?,Ci+1?<Ci?),那么令 B i + 1 ← B i + 1 ? 1 , C i + 1 ← C i + 1 B_{i+1}\gets B_{i+1}-1,C_{i+1}\gets C_{i}+1 Bi+1?Bi+1??1,Ci+1?Ci?+1,最后的答案不会更劣(证明可以手模一下),不停操作下去,最终可以得到结论。

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

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

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

文章来源:https://blog.csdn.net/dygxczn/article/details/134954393
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。