正文 

当前位置： 首页 > java > java教程

bzoj1588：[hnoi2002]营业额统计

Tyw_ei Tyw_ei     2022-10-02     344

关键词：

1588: [HNOI2002]营业额统计

             Time Limit: 5 Sec??Memory Limit: 162 MB

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

12

Solution

平衡树裸体....
可以用链表写，不过像我这种没有什么追求的人就打了个平衡树走人
顺便安利一波同组大佬写的链表

平衡树：

#include <bits/stdc++.h>
using namespace std;
#define inf 2147483647
struct node{
????node *son[2],*father;
????int val,size,count;
????node(int v=0,node *f=NULL){
????????val=v,father=f;son[1]=son[0]=NULL; 
????????size=count=1;
????}
}*root;
?
inline bool son(node *f,node *t){return f->son[1]==t;}
inline int size(node *t){return t==NULL?0:t->size+t->count;}
inline void update(node *t){t->size=size(t->son[0])+size(t->son[1])+t->count;}
?
inline void rotate(node *t){
??????node *f=t->father,*g=f->father;
??????bool a=son(f,t),b=!a;
??????f->son[a]=t->son[b];
??????if(t->son[b]!=NULL)
????????t->son[b]->father=f;
??????f->father=t;
??????t->father=g;
??????t->son[b]=f;
??????if(g!=NULL)
????????g->son[son(g,f)]=t;
??????else root=t;
??????update(f);update(t);
}
?
inline void splay(node *t,node *p){
????while(t->father!=p){
????????node *f=t->father,*g=f->father;
????????if(g==p)rotate(t);
????????else if(son(f,t)^son(g,f))
????????????rotate(t),rotate(t);
????????else rotate(f),rotate(t);
????}
}
?
inline void insert(int val){
????if(root==NULL){
????????root=new node(val);
????????return;
????}
????for(node *t=root;t!=NULL;t=t->son[val>t->val]){
????????t->size++;
????????if(val==t->val){
????????????t->count++;splay(t,NULL);
????????????return;
????????}
????????if(t->son[val>t->val]==NULL){
????????????bool a=val>t->val,b=!a;
????????????t->son[a]=new node(val,t);
????????????splay(t->son[a],NULL);
????????????return;
????????}
????}
}
?
inline int lower(int val){
????int rtn=-inf;
????for(node *t=root;t!=NULL;){
????????if(val>=t->val){
????????????rtn=t->val;
????????????t=t->son[1];
????????}else t=t->son[0];
????}return rtn;
}
?
inline int upper(int val){
????int rtn=-inf;
????for(node *t=root;t!=NULL;){
????????if(val<t->val){
????????????rtn=t->val;
????????????t=t->son[0];
????????}else t=t->son[1];
????}return rtn;
}
?
int main(){
????int n;scanf("%d",&n);
????int ans;scanf("%d",&ans);insert(ans);
????insert(inf);
????for(int i=2;i<=n;i++){
????????int x,tmp=inf;scanf("%d",&x);
????????int lowr=lower(x);
????????int uppr=upper(x);
????????if(lowr!=-inf)tmp=min(tmp,abs(lowr-x));
????????if(uppr!=-inf)tmp=min(tmp,abs(uppr-x));
????????ans+=tmp;
????????insert(x);
????}
????printf("%d",ans);
????return 0;
}

链表：

#include <bits/stdc++.h> 
using namespace std;

const int maxn = 5e4 + 10;
struct node {
    int l, r, v;
}T[maxn];
int pos[maxn];
bool cmp(int x, int y) {
    return T[x].v < T[y].v;
}
void erase(int p) {
    T[T[p].l].r = T[p].r;
    T[T[p].r].l = T[p].l;
}
int ans;
int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &T[i].v), pos[i] = i;
    sort(pos + 1, pos + 1 + n, cmp);
    for (int i = 2; i <= n; i++) {
        T[pos[i - 1]].r = pos[i];
        T[pos[i]].l = pos[i - 1];
    }
    for (int i = n; i > 1; i--) {
        int now = 1e9;
        if (T[i].l) now = min(now, abs(T[i].v - T[T[i].l].v));
        if (T[i].r) now = min(now, abs(T[i].v - T[T[i].r].v));
        erase(i);
        ans += now;
    }
    ans += T[1].v;
    return 0 * printf("%d", ans);
}

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