正文

[bzoj1588][hnoi2002]营业额统计无旋treap

LadyLex  LadyLex  2022-09-08  772

关键词：

[HNOI2002]营业额统计

时间限制: 5 Sec 内存限制: 162 MB

题目描述

营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：该天的最小波动值当最小波动值越大时，就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。第一天的最小波动值为第一天的营业额。 ? 输入输出要求

输入

第一行为正整数，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数(有可能有负数) ，表示第i天公司的营业额。

输出

输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。

样例输入

样例输出

提示

结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

该题数据bug已修复.----2016.5.15

题解：

这题的思路和之前一道“宠物收养所”很像，我们只需要查找每个数的前驱和后继，然后去做差绝对值较小的即可.

（这道题其实可以STL set水过去，为什么我要打无旋Treap233）

代码见下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <ctime>
 5 #include <cstdlib>
 6 using namespace std;
 7 int n;
 8 struct Treap
 9 {
10     Treap *ch[2];
11     int val,size,key;
12     Treap(){val=size=0;key=rand();ch[0]=ch[1]=NULL;}
13     inline void update(){size=1+ch[0]->size+ch[1]->size;}
14 }*null=new Treap(),*root=null;
15 typedef pair<Treap*,Treap*> D;
16 inline Treap* newTreap(int v)
17 {
18     Treap *o=new Treap();
19     o->ch[0]=o->ch[1]=null;
20     o->val=v;o->size=1;
21     return o;
22 }
23 Treap *merge(Treap *a,Treap *b)
24 {
25     if(a==null)return b;
26     if(b==null)return a;
27     if(a->key < b->key)
28         {a->ch[1]=merge(a->ch[1],b);a->update();return a;}
29     else
30         {b->ch[0]=merge(a,b->ch[0]);b->update();return b;}
31 }
32 D split(Treap *o,int k)
33 {
34     if(o==null) return D(null,null);
35     D y;
36     if(o->ch[0]->size >=k)
37         {y=split(o->ch[0],k);o->ch[0]=y.second;o->update();y.second=o;}
38     else
39         {y=split(o->ch[1],k-o->ch[0]->size-1);o->ch[1]=y.first;o->update();y.first=o;}
40     return y;
41 }
42 int getrank(Treap *o,int v)
43 {
44     if(o==null)return 0;
45     return o->val >=v?getrank(o->ch[0],v):getrank(o->ch[1],v)+o->ch[0]->size+1;
46 }
47 inline int getval(int rank)
48 {
49     D x=split(root,rank-1);
50     D y=split(x.second,1);
51     int ret=y.first->val;
52     root=merge(merge(x.first,y.first),y.second);
53     return ret;
54 }
55 inline int query(int val)
56 {
57     int pre=getval(getrank(root,val));
58     int back=getval(getrank(root,val)+1);
59     return min(abs(back-val),abs(pre-val));
60 }
61 inline void insert(int val)
62 {
63     int k=getrank(root,val);
64     D x=split(root,k);
65     Treap *o=newTreap(val);
66     root=merge(merge(x.first,o),x.second);
67 }
68 int main()
69 {
70     scanf("%d",&n);int x,ans=0;
71     while(n--)
72     {
73         scanf("%d",&x);
74         ans+=query(x);
75         insert(x);
76     }
77     printf("%d",ans);
78 }

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是最直接的方法，但我感觉离散一波应该可以做出来（没仔细想过）现在没有很追求代码优美，感觉得先打的对打的... 查看详情