首页 > 代码库 > 1367: [Baltic2004]sequence

1367: [Baltic2004]sequence

1367: [Baltic2004]sequence

Time Limit: 20 Sec  Memory Limit: 64 MB
Submit: 1090  Solved: 432
[Submit][Status][Discuss]

Description

技术分享

Input

技术分享

Output

一个整数R

Sample Input

7
9
4
8
20
14
15
18

Sample Output

13

HINT

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

Source

 

【题解】:

详见:《左偏树的特点及其应用》(P18-20)

【代码】:

//左偏树,最短的高级数据结构了 #include<cstdio>#include<cstdlib>#include<iostream>using namespace std;const int N=1e6+10;int n,tot,count,root[N],l[N],r[N],z[N],num[N],cnt[N];struct node{    int l,r,dis,w;}heap[N];int merge(int a,int b){    if(!a||!b) return a+b;     if(heap[a].w<heap[b].w) swap(a,b);    heap[a].r=merge(heap[a].r,b);    if(heap[heap[a].l].dis<heap[heap[a].r].dis)        swap(heap[a].l,heap[a].r);    heap[a].dis=heap[heap[a].r].dis+1;    return a;}int pop(int a){    return merge(heap[a].l,heap[a].r);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",&z[i]),z[i]-=i;    for(int i=1;i<=n;i++){        ++tot;        l[tot]=r[tot]=i;        num[tot]=cnt[tot]=1;        root[tot]=++count;        heap[count].w=z[i];                while(tot>1&&heap[root[tot]].w<heap[root[tot-1]].w){            --tot;            root[tot]=merge(root[tot],root[tot+1]);            num[tot]+=num[tot+1];            cnt[tot]+=cnt[tot+1];            r[tot]=r[tot+1];            for(;cnt[tot]*2>num[tot]+1;cnt[tot]--)                root[tot]=pop(root[tot]);        }    }    long long ans=0;    for(int i=1;i<=tot;i++)        for(int j=l[i],w=heap[root[i]].w;j<=r[i];j++)            ans+=abs(z[j]-w);    cout<<ans;    return 0;}

 

 

 

 

1367: [Baltic2004]sequence