正文

bzoj1588[hnoi2002]营业额统计

Doggu  Doggu  2022-09-02  758

关键词：

1588: [HNOI2002]营业额统计

Description

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

Input

第一行为正整数，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数(有可能有负数) ，表示第i天公司的营业额。天数n<=32767,每天的营业额ai <= 1,000,000。最后结果T<=2^31

Output

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

Sample Input

6
5
1
2
5
4
6

Sample Output

HINT

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

　　这是一道裸题，BST。可以用TREAP，十分经典。不多说了。（LMY给我们一个小时做）

 1 /**************************************************************
 2     Problem: 1588
 3     User: Doggu
 4     Language: C++
 5     Result: Accepted
 6     Time:196 ms
 7     Memory:1448 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 #include <cmath>
12 #include <algorithm>
13  
14 const int N = 40000;
15 struct Node {
16     int key, rd;
17     Node *ch[2];
18     int cmp(int x) {
19         if(x==key) return -1;
20         return x>key;
21     }
22 }pool[N], *tail=pool, *root=pool, *null=pool;
23  
24 int rand() {
25     static int seed=1000007;
26     return seed=(int)seed*48271LL%2147483647;
27 }
28  
29 Node* newnode(int x) {
30     Node *nd = tail++;
31     nd->ch[0]=nd->ch[1]=null;
32     nd->key=x;nd->rd=rand();
33     return nd;
34 }
35  
36 void rotate(Node *&nd,int d) {//d=0 right(1) to left(0) d=1 left(0) to right(1)
37     Node *k=nd->ch[d^1];nd->ch[d^1]=k->ch[d];k->ch[d]=nd;nd=k;
38 }
39  
40 int temp;
41 void query(Node *nd,int x) {
42     if(nd==null) temp=std::min(temp,x);
43     int d=nd->cmp(x);
44     temp=std::min(temp,std::abs(nd->key-x));
45     if(d==-1||nd->ch[d]==null) return ;
46     query(nd->ch[d],x);
47 }
48  
49 void insert(Node *&nd,int x) {
50     if(nd==null) nd=newnode(x);
51     else {
52         int d=nd->cmp(x);
53         if(d==-1) return ;
54         //printf("INSERT:%d %d %d
",nd->key,x,d);
55         insert(nd->ch[d],x);
56         if(nd->ch[d]->rd>nd->rd) rotate(nd,d^1);
57     }
58 }
59  
60 /*void print(Node *nd) {
61     if(nd==null) return ;
62     print(nd->ch[0]);
63     printf("%d ",nd->key);
64     print(nd->ch[1]);
65 }*/
66  
67 int main() {
68     null=newnode(0);
69     int n, x, ans = 0;
70     scanf("%d",&n);
71     for( int i = 1; i <= n; i++ ) {
72         scanf("%d",&x);
73         temp=0x3f3f3f3f;query(root,x);ans+=temp;
74         insert(root,x);
75         //printf("print:");print(root);printf("
");
76     }
77     printf("%d",ans);
78     return 0;
79 }

View Code

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