[Baltic2004]sequence

题目描述：

给定一个序列t1,t2,...,tn ，求一个递增序列z1<z2<...<zn ，使得R=|t1−z1|+|t2−z2|+...+|tn−zn| 的值最小。本题中，我们只需要求出这个最小的R值。

样例输入

7 9 4 8 20 14 15 18

样例输出

提示

所求的Z序列为6,7,8,13,14,15,18.

R=13

题解：

考虑t1>=t2>=t3>=t4这种递减的情况，那么整个z只需取t数组的中位数即可。

由于z是递增数列,不能全取一样的数。所以我们把t[i]-i；保证z数组就可以取一样的数了 且不会影响答案，因为t[i]-i的同时，求出来z[i]也是减了i的

那么我们就采取分治的思想，把原数列分成m个递减区间,然后分别取中位数，使得该区间的差值尽量小.

设X[i]为没个区间的中位数，那么如果X[i]<X[i-1]时不满足z[i]递增的题意，所以要合并，且合并后的答案会更优。(见网上的论文证明)

以下是详细做法和证明：

还有一个我的傻逼错误

ldis()和rdis()没写return 居然函数没有返回值不warning,浪费了很久

代码如下：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<cstdlib>

 using namespace std;

 const int N=;

 typedef long long ll;

 ll gi()

 {

     ll str=;char ch=getchar();

     while(ch>'' || ch<'')ch=getchar();

     while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();

     return str;

 }

 struct node

 {

     int dis,size,ls,rs;ll x;

     node *l,*r;

     int ldis(){return l?l->dis:;}

     int rdis(){return r?r->dis:;}

 }T[N];

 ll a[N];node *root[N],*pos=T;

 ll st[N],top=;

 ll ans=;

 void updata(node *&R)

 {

     if(R)R->size=(R->l?R->l->size:)+(R->r?R->r->size:)+;

 }

 node *merge(node *p,node *q)

 {

     if(!p||!q){return p?p:q;}

     if(p->x<q->x)swap(p,q);

     if(p->ls>q->ls)p->ls=q->ls;

     if(p->rs<q->rs)p->rs=q->rs;

     p->r=merge(p->r,q);

     if(p->ldis()<p->rdis())swap(p->l,p->r);

     p->dis=p->rdis()+;

     updata(p);

     return p;

 }

 void Delet(int x)

 {

     node *y=root[x];

     root[x]=merge(root[x]->r,root[x]->l);

     root[x]->ls=y->ls;root[x]->rs=y->rs;

     y->l=y->r=NULL;y->size=;

 }

 int main()

 {

     int n=gi(),k;

     for(int i=;i<=n;i++){

         a[i]=gi()-i;

         pos->l=pos->r=NULL;pos->x=a[i];pos->size=;

         pos->ls=pos->rs=i;

         root[i]=pos;pos->dis=;

         pos++;

     }

     int now;

     st[++top]=;

     for(int i=;i<=n;i++){

         now=i;

         while(top){

             k=st[top];

             if(root[k]->x>root[now]->x){

                 top--;

                 root[k]=merge(root[now],root[k]);

                 while((root[k]->size<<)>(root[k]->rs-root[k]->ls+))Delet(k);

                 now=k;

                 if(!top){

                     st[++top]=now;

                     break;

                 }

             }

             else{

                 st[++top]=now;

                 break;

             }

         }

     }

     while(top){

         k=st[top];top--;

         for(int i=root[k]->ls;i<=root[k]->rs;i++)ans+=abs(root[k]->x-a[i]);

     }

     cout<<ans;

     return ;

 }

巴特西

[Baltic2004]sequence

样例输入

样例输出

提示

最新文章

热门文章