正文

洛谷2234bzoj1588hnoi2002营业额统计

Driver_Lao  Driver_Lao  2022-10-05  125

关键词：

【题解】

　　treap模板题，直接用Treap维护前驱、后继，每次找到更接近当前val的加上就好了。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define ls (a[u].l)
 4 #define rs (a[u].r)
 5 #define LL long long
 6 using namespace std;
 7 const int maxn=200010;
 8 int n,k,x,y,z,v,tot,root;
 9 struct treap{int l,r,v,rnd,size;}a[maxn];
10 LL sum=0;
11 inline void read(int &k){
12     k=0; int f=1; char c=getchar();
13     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
14     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
15     k*=f;
16 }
17 void newnode(int v){a[++tot]=(treap){0,0,v,rand()+1,1};}
18 void update(int u){a[u].size=a[ls].size+a[rs].size+1;}
19 void split(int u,int k,int &x,int &y){
20     if(!k){x=0; y=u; return;}
21     if(a[u].size==k){x=u; y=0; return;}
22     if(a[ls].size>=k) split(ls,k,x,ls),y=u;
23     else split(rs,k-a[ls].size-1,rs,y),x=u;
24     update(u);
25 }
26 int merge(int x,int y){
27     if(!(x*y)) return x+y;
28     if(a[x].rnd>a[y].rnd){
29         a[y].l=merge(x,a[y].l); update(y); return y;
30     }
31     else{
32         a[x].r=merge(a[x].r,y); update(x); return x;
33     }
34 }
35 int qrank(int u,int val){
36     if(!u) return 0;
37     if(a[u].v>=val) return qrank(ls,val);
38     return qrank(rs,val)+a[ls].size+1;
39 }
40 int qval(int u,int k){
41     if(a[ls].size+1==k) return a[u].v;
42     return a[ls].size>=k?qval(ls,k):qval(rs,k-a[ls].size-1);
43 }
44 int main(){
45     srand(20020705); root=tot=1; a[root].v=2e9; a[root].size=1;
46     read(n);
47     for(int i=1;i<=n;i++){
48         read(v); 
49         if(i<=2) sum+=abs(v-sum);
50         else{
51             int tmp=qrank(root,v),ans=0X7f7f7f;
52             if(tmp) ans=abs(v-qval(root,tmp));
53             if(tmp<a[root].size) ans=min(ans,abs(v-qval(root,tmp+1)));
54             sum+=ans;
55         }
56         split(root,qrank(root,v),x,y);
57         newnode(v); root=merge(merge(x,tot),y);
58     }
59     return printf("%lld",sum),0;
60 }

View Code

链表bzoj1588:[hnoi2002]营业额统计

1588:[HNOI2002]营业额统计TimeLimit:5Sec MemoryLimit:162MBSubmit:17555 Solved:7179[Submit][Status][Discuss]Description营业额统计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]营业额统计

1588:[HNOI2002]营业额统计TimeLimit:5Sec??MemoryLimit:162MBDescription营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成... 查看详情

[bzoj1588][hnoi2002]营业额统计

[BZOJ1588][HNOI2002]营业额统计试题描述营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额... 查看详情

洛谷:p2234[hnoi2002]营业额统计

原题地址：https://www.luogu.org/problemnew/show/P2234题目简述给定一个序列，对于每一个数都要查询：序列中在这个数前与这个数最接近的数是什么？然后将最接近的数字与这个数字的差累加。（序列第一个数字直接加自己）思路查询... 查看详情

bzoj1588[hnoi2002]营业额统计

1588:[HNOI2002]营业额统计Description营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分... 查看详情

bzoj1588[hnoi2002]营业额统计splay模板

1588:[HNOI2002]营业额统计TimeLimit:5Sec MemoryLimit:162MBSubmit:16189 Solved:6482[Submit][Status][Discuss]Description营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营... 查看详情

洛谷p2234[hnoi2002]营业额统计

...ger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营... 查看详情

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]营业额统计

【传送门：BZOJ1588】简要题意：　　给出n个数，每个数只能前面的任意一个数相减，要求差的绝对值最小，求出所有数做的差的最小绝对值的和（第一个数做得差的最小绝对值就是它自己）题解：　　伸展树SPLAY，将n个数逐个放... 查看详情

bzoj1588：[hnoi2002]营业额统计

Description营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当... 查看详情

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

[HNOI2002]营业额统计时间限制: 5Sec 内存限制: 162MB题目描述营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账... 查看详情

bzoj1588:[hnoi2002]营业额统计双向链表/splay/treap

1588:[HNOI2002]营业额统计 Description营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额... 查看详情