首页 > 代码库 > 1367: [Baltic2004]sequence
1367: [Baltic2004]sequence
1367: [Baltic2004]sequence
Time Limit: 20 Sec Memory Limit: 64 MBSubmit: 1090 Solved: 432
[Submit][Status][Discuss]
Description
Input
Output
一个整数R
Sample Input
7
9
4
8
20
14
15
18
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。