首页 > 代码库 > 【codevs1296】 营业额统计
【codevs1296】 营业额统计
http://codevs.cn/problem/1296/ (题目链接)
题意
给出一个序列，对于每一个数，找出之前与它相差最小的数，两者相减取绝对值加入答案。
Solution
最近bzoj炸了，无奈只能上codevs刷题了。。好久没上过codevs了，实在是里面题目的数据水上了新高度，万一犯了什么错误还AC了，那就有点尴尬了。。。
这道题只有单点插入和查询前驱后继的操作，其实完全可以set水过去，算了就当splay练手吧。。
这道题要求splay满足二叉搜索树的性质，而对序列的顺序没有要求，于是我们每次在平衡树中插入一个节点，然后splay到根节点，因为平衡树满足二叉搜索树的性质，这样的话查询前驱和后继的时候就可以大大减少复杂度。
代码
// codevs1296#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf (1<<30)#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;int fa[maxn],tr[maxn][2],val[maxn];int n,size,rt,t1,t2;void rotate(int x,int &k) { int y=fa[x],z=fa[y],l,r; if (tr[y][0]==x) l=0;else l=1;r=l^1; if (k==y) k=x; else tr[z][tr[z][1]==y]=x; fa[x]=z;fa[y]=x;fa[tr[x][r]]=y; tr[y][l]=tr[x][r];tr[x][r]=y;}void splay(int x,int &k) { while (x!=k) { int y=fa[x],z=fa[y]; if (y!=k) { if (tr[y][0]==x ^ tr[z][0]==y) rotate(x,k); else rotate(y,k); } rotate(x,k); }}bool insert(int &k,int x,int f) { if (k==0) {k=++size;val[k]=x,fa[k]=f,splay(k,rt);return 1;} if (val[k]==x) return 0; if (x<val[k]) return insert(tr[k][0],x,k); else return insert(tr[k][1],x,k);}void query_pr(int k) { if (tr[k][0]==0) return; k=tr[k][0]; while (tr[k][1]) k=tr[k][1]; t1=val[k];}void query_nx(int k) { if (tr[k][1]==0) return; k=tr[k][1]; while (tr[k][0]) k=tr[k][0]; t2=val[k];}int main() { scanf("%d",&n); int ans=0; for (int x,i=1;i<=n;i++) { scanf("%d",&x); if (!insert(rt,x,0)) continue; t1=-inf;t2=inf; query_pr(rt); query_nx(rt); if (i==1) ans+=x; else ans+=min(x-t1,t2-x); } printf("%d",ans); return 0;}
【codevs1296】 营业额统计
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。