BZOJ 1367 [Baltic2004]sequence

Description

给定一个序列\(t_1,t_2,\dots,t_N\),求一个递增序列\(z_1<z_2<\dots<z_N\)，使得\(R=|t_1-z_1|+|t_2-z_2|+\dots+|t_N-z_N|\)的值最小，本题中，我们只需求出这个最小的\(R\)值

Input

第\(1\)行为\(N(1\le N\le10^6)\)

第\(2\)行到第\(N+1\)行，每行一个整数。第\(K+1\)行为\(t_k(0\le t_k \le 2\times 10^9)\)

---

思路：

如果我们需要求一个非递减的\(z\)

考虑特殊情况

注意到对一个递增的序列，有\(z_i=t_i\)

对一个递减的序列，有\(z_i\)为\(t_i\)的中位数

所以猜测可以找到一种区间的划分，使每一段区间的\(z_i\)都是这段区间\(t_i\)的中位数

感性理解一下感觉是对的。

实现起来需要动态维护末尾的区间的中位数，我们每次新进一个元素的时候，自己成一个区间，然后比一下和末尾的区间的中位数，比\(\text{Ta}\)小就合并了。注意到可以用堆维护中位数，然后合并就可并堆了。

最后一点，上面的情况都是针对非递减的情况，改成递增也很简单，把\(t_i=t_i-i\)就行了，感性理解一下似乎挺容易的。

---

Code:

#include 
    
     #include 
     
      #include 
      
       #define ll long longconst int N=1e6+10;int n,m,dis[N],key[N],rig[N],root[N],siz[N],ch[N][2];#define ls ch[x][0]#define rs ch[x][1]int Merge(int x,int y){    if(!x||!y) return x+y;    if(key[x]
       
        >1
        
         key[root[m]])            root[m-1]=Merge(root[m-1],root[m]),rig[m-1]=rig[m],--m,maintain();    }    ll ans=0;    for(int i=1;i<=m;i++)        for(int j=rig[i-1]+1;j<=rig[i];j++)            ans=ans+abs(key[j]-key[root[i]]);    printf("%lld\n",ans);    return 0;}
        
       
      
     
    

---

2018.12.10