首页 > 代码库 > BZOJ 1588 HNOI2002 营业额统计 裸Treap
BZOJ 1588 HNOI2002 营业额统计 裸Treap
题目大意:。。。题目描写叙述不全看这里好了
给定一个序列 对于每一个元素我们定义该数的最小波动值为这个数与前面全部数的差中的最小值(第一个数的最小波动值为第一个数本身) 求最小波动值之和
找近期的数仅仅须要找前驱和后继即可了 平衡树的基本操作 不多说了
然后——
此题多组数据!!尼玛!!看题目描写叙述这也是单组数据啊。!什么**情况??
并且多组数据尼玛也就算了!。输入数据还不全!
!假设读到EOF须要依照0处理。尼玛这上哪里想去啊!
于是此题不看题解无法AC 鉴定完成
60%达成 还剩四道题 水水吧。
。。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct abcd{ abcd *ls,*rs; int key,num; abcd(int x); }*null=new abcd(0),*root=null; abcd :: abcd(int x) { ls=rs=null; key=rand(); num=x; } void Zig(abcd *&x) { abcd *y=x->ls; x->ls=y->rs; y->rs=x; x=y; } void Zag(abcd *&x) { abcd *y=x->rs; x->rs=y->ls; y->ls=x; x=y; } void Insert(abcd *&x,int y) { if(x==null) { x=new abcd(y); return ; } if(y==x->num) return ; if(y<x->num) { Insert(x->ls,y); if(x->ls->key>x->key) Zig(x); } else { Insert(x->rs,y); if(x->rs->key>x->key) Zag(x); } } int Pred(abcd *x,int y) { if(x==null) return 0xefefefef; if(y<x->num) return Pred(x->ls,y); return max( x->num , Pred(x->rs,y) ); } int Secc(abcd *x,int y) { if(x==null) return 0x7fffffff; if(y>x->num) return Secc(x->rs,y); return min( x->num , Secc(x->ls,y) ); } int n,ans; int main() { int i,x; srand(19980402); while(~scanf("%d",&n) ) { root=null;ans=0; for(i=1;i<=n;i++) { if(scanf("%d",&x)==EOF)x=0; int pred=Pred(root,x),secc=Secc(root,x); if(i^1) ans+=min( x-pred , secc-x ); else ans+=x; Insert(root,x); } cout<<ans<<endl; } }
BZOJ 1588 HNOI2002 营业额统计 裸Treap
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。