首页 > 其他 > 详细

[BZOJ 1367] sequence

时间:2018-08-25 21:06:34      阅读:199      评论:0      收藏:0      [点我收藏+]

题目传送-BZOJ1367

题意:

给定序列\(t\),求一个严格递增序列A。
最小化\(R=\sum_{i=1}^{n}|A_i-t_i|\)
输出\(A\)
\(n\le1000000\)

题解

可并堆:
请见:一篇论文
线段树:
只要卡卡空间,支持区间加一次函数之类的就行了

过程:

智障错误:
1.Merge比较深度的时候忘加dep这层。。
2.中位数的去留处理错误,本来写了小根堆,发现它会在小段的时候把大段的中位数直接删掉。。

代码:

const int N=1000010;
int n;
ll t[N];
ll hp[N];
int ch[N][2],dep[N],sz[N];
int stk[N],top=0;
int l[N],r[N];
inline int Up(int x) {return (x>>1)+(x&1);}
inline int Merge(int u,int v) {
    if(!u || !v) return u+v;
    if(hp[u]<hp[v]) swap(u,v);
    ch[u][1]=Merge(ch[u][1],v);
    if(dep[ch[u][1]]>dep[ch[u][0]]) swap(ch[u][0],ch[u][1]);
    dep[u]=dep[ch[u][1]]+1;
    sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1;
    return u;
}

signed main() {
    read(n);
    for(int i=1;i<=n;i++) read(t[i]),t[i]-=i;
    for(int i=1;i<=n;i++) hp[i]=t[i],sz[i]=1;
    for(int i=1;i<=n;i++) {
        stk[++top]=i; l[top]=i; r[top]=i;
        while(hp[stk[top-1]]>hp[stk[top]] && top>1) {
            int u=Merge(stk[top-1],stk[top]);
            // printf("%d %d %d\n",sz[u],stk[1],u); 
            r[top-1]=r[top];
            int bd=Up(r[top-1]-l[top-1]+1);
            while(sz[u]>bd) {
                u=Merge(ch[u][0],ch[u][1]);
            }
            stk[--top]=u;
        }
    }
    // printf("top=%d\n",top);
    // for(int i=1;i<=top;i++) printf("%d ",stk[i]); puts("");
    // for(int i=1;i<=top;i++) printf("%d %d %d\n",l[i],r[i],sz[stk[i]]);
    ll ans=0;
    for(int i=1;i<=top;i++)
        for(int j=l[i];j<=r[i];j++){
            ans+=abs(hp[stk[i]]-t[j]);
        }
    printf("%lld\n",ans);
    return 0;
}

用时:30min

[BZOJ 1367] sequence

原文:https://www.cnblogs.com/functionendless/p/9535247.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!