关键词:
【传送门:BZOJ1588】
简要题意:
给出n个数,每个数只能前面的任意一个数相减,要求差的绝对值最小,求出所有数做的差的最小绝对值的和(第一个数做得差的最小绝对值就是它自己)
题解:
伸展树SPLAY,将n个数逐个放进伸展树中,在放一个数时,先求出这个数在树中的前驱和后继,然后比较哪个最接近这个数,然后ans加上前驱或后继与这个数的差的绝对值,然后把这个数放进伸展树里
参考代码:
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct node { int n,d,f,c,son[2]; }a[110000];int len,root; void add(int d,int f) { len++; a[len].d=d;a[len].c=a[len].n=1; a[len].son[1]=a[len].son[0]=0;a[len].f=f; if(d<a[f].d) a[f].son[0]=len; else a[f].son[1]=len; } void update(int x) { int lc=a[x].son[0],rc=a[x].son[1]; a[x].c=a[x].n+a[lc].c+a[rc].c; } int findip(int d) { int x=root; while(a[x].d!=d) { if(a[x].d>d) { if(a[x].son[0]==0)break; else x=a[x].son[0]; } else { if(a[x].son[1]==0)break; else x=a[x].son[1]; } } return x; } void rotate(int x,int w) { int f=a[x].f,ff=a[f].f; int r,R; r=a[x].son[w];R=f; a[R].son[1-w]=r; if(r!=0)a[r].f=R; r=x;R=ff; if(a[R].son[0]==f)a[R].son[0]=r; else a[R].son[1]=r; a[r].f=R; r=f;R=x; a[R].son[w]=r; a[r].f=R; update(f); update(x); } void splay(int x,int rt) { while(a[x].f!=rt) { int f=a[x].f,ff=a[f].f; if(ff==rt) { if(a[f].son[0]==x)rotate(x,1); else rotate(x,0); } else { if(a[f].son[0]==x && a[ff].son[0]==f){rotate(f,1);rotate(x,1);} else if(a[f].son[1]==x && a[ff].son[0]==f){rotate(x,0);rotate(x,1);} else if(a[f].son[0]==x && a[ff].son[1]==f){rotate(x,1);rotate(x,0);} else if(a[f].son[1]==x && a[ff].son[1]==f){rotate(f,0);rotate(x,0);} } } if(rt==0)root=x; } void ins(int d) { if(root==0) { add(d,0);root=len; return ; } int x=findip(d); if(d==a[x].d) { a[x].n++; update(x); splay(x,0); } else { add(d,x); update(x); splay(len,0); } } void del(int d) { int x=findip(d);splay(x,0); if(d!=a[x].d)return ; if(a[x].n>1){a[x].n--;update(x);return ;} if(a[x].son[0]==0 && a[x].son[1]==0){root=0;len=0;} else if(a[x].son[0]!=0 && a[x].son[1]==0){root=a[x].son[0];a[root].f=0;} else if(a[x].son[1]!=0 && a[x].son[0]==0){root=a[x].son[1];a[root].f=0;} else { int p=a[x].son[0]; while(a[p].son[1]!=0)p=a[p].son[1]; splay(p,x); int r,R; r=a[x].son[1];R=p; a[R].son[1]=r; a[r].f=R; root=R;a[root].f=0; update(R); } } int findqianqu(int d) { int x=findip(d);splay(x,0); if(d<a[x].d && a[x].son[0]!=0) { x=a[x].son[0]; while(a[x].son[1]!=0)x=a[x].son[1]; } if(d<a[x].d)x=0; return x; } int findhouji(int d) { int x=findip(d);splay(x,0); if(d>a[x].d && a[x].son[1]!=0) { x=a[x].son[1]; while(a[x].son[0]!=0)x=a[x].son[0]; } if(d>a[x].d)x=0; return x; } int findpaiming(int d) { int x=findip(d); splay(x,0); return a[a[x].son[0]].c+1; } int findshuzi(int k) { int x=root; while(1) { int lc=a[x].son[0],rc=a[x].son[1]; if(k<=a[lc].c)x=lc; else if(k>a[lc].c+a[x].n){k-=a[lc].c+a[x].n;x=rc;} else break; } return a[x].d; } int n; int main() { scanf("%d",&n);len=0;root=0; int ans=0;int d; scanf("%d",&d);ans+=d;ins(d); for(int i=2;i<=n;i++) { scanf("%d",&d); int ss=999999999; int lc=findqianqu(d),rc=findhouji(d); if(lc!=0) ss=abs(a[lc].d-d); if(rc!=0) ss=min(abs(a[rc].d-d),ss); ans+=ss; ins(d); } printf("%d ",ans); return 0; }
bzoj1588:[hnoi2002]营业额统计
1588:[HNOI2002]营业额统计TimeLimit:5Sec??MemoryLimit:162MBDescription营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本,账本上记录了公司成... 查看详情
bzoj1588:[hnoi2002]营业额统计treap
1588:[HNOI2002]营业额统计TimeLimit: 5Sec MemoryLimit: 162MBSubmit: 13902 Solved: 5225[Submit][Status][Discuss]Description营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是 查看详情
bzoj1588:[hnoi2002]营业额统计[bst]
1588:[HNOI2002]营业额统计TimeLimit: 5Sec MemoryLimit: 162MBSubmit: 14151 Solved: 5366[Submit][Status][Discuss]Description营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是 查看详情
bzoj1588[hnoi2002]营业额统计treap
1588:[HNOI2002]营业额统计TimeLimit: 5Sec MemoryLimit: 162MBSubmit: 17740 Solved: 7298[Submit][Status][Discuss]Description营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是 查看详情
[bzoj1588][hnoi2002]营业额统计
[BZOJ1588][HNOI2002]营业额统计试题描述营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额... 查看详情
bzoj1588[hnoi2002]营业额统计
1588:[HNOI2002]营业额统计Description营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额。分... 查看详情
bzoj1588[hnoi2002]营业额统计splay模板
1588:[HNOI2002]营业额统计TimeLimit:5Sec MemoryLimit:162MBSubmit:16189 Solved:6482[Submit][Status][Discuss]Description营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营... 查看详情
bzoj1588:[hnoi2002]营业额统计(代码片段)
1588:[HNOI2002]营业额统计TimeLimit: 5Sec MemoryLimit: 162MBDescription营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本,账... 查看详情
bzoj1588:[hnoi2002]营业额统计
【算法】平衡树(treap)||双向链表【题解】#include<cstdio>#include<algorithm>#include<ctime>usingnamespacestd;constintmaxn=100010,inf=0x3f3f3f3f;intn,sum,ans,sz,root;structcyc{intl,r,rnd,num;}t[maxn]; 查看详情
bzoj1588[hnoi2002]营业额统计
1251:序列终结者TimeLimit: 20Sec MemoryLimit: 162MBSubmit: 3773 Solved: 1579[Submit][Status][Discuss]Description 网上有许多题,就是给定一个序列,要你支持几种操作:A、B、C、D。一看另一道题,又是一个序列 要支持... 查看详情
bzoj1588[hnoi2002]营业额统计
传送门 平衡树常规题,给出两种实现算法Treap版:1//OJ16102//byCydiater3//2016.9.14#include<iostream>5#include<cstdio>6#include<cstdlib>7#include<cstring>8#include<iomanip>9#include<str 查看详情
bzoj1588:[hnoi2002]营业额统计
Description营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当... 查看详情
[bzoj1588][hnoi2002]营业额统计无旋treap
[HNOI2002]营业额统计时间限制: 5Sec 内存限制: 162MB题目描述营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本,账... 查看详情
洛谷2234bzoj1588hnoi2002营业额统计
【题解】 treap模板题,直接用Treap维护前驱、后继,每次找到更接近当前val的加上就好了。1#include<cstdio>2#include<algorithm>3#definels(a[u].l)4#definers(a[u].r)5#defineLLlonglong6usingnamespacestd;7constintmaxn=200010;8intn,k 查看详情
bzoj1588:[hnoi2002]营业额统计
【传送门:BZOJ1588】简要题意: 给出n个数,每个数只能前面的任意一个数相减,要求差的绝对值最小,求出所有数做的差的最小绝对值的和(第一个数做得差的最小绝对值就是它自己)题解: 伸展树SPLAY,将n个数逐个放... 查看详情
bzoj1588:[hnoi2002]营业额统计双向链表/splay/treap
1588:[HNOI2002]营业额统计 Description营业额统计Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额... 查看详情
[bzoj1588][hnoi2002]营业额统计(splay)
...ger拿出了公司的账本,账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日,大减价或者是其他情况的时候,营业额会出现一定的波动,当然一定的波动是能够接受的,但是在某些时候营... 查看详情
bzoj1588:[hnoi2002]营业额统计splay瞎写
最近各种瞎写数论题,感觉需要回顾一下数据结构写一发splay冷静一下(手速过慢,以后要多练练)用splay是最直接的方法,但我感觉离散一波应该可以做出来(没仔细想过)现在没有很追求代码优美,感觉得先打的对打的... 查看详情