首页 > 代码库 > HNOI 2002 营业额统计

HNOI 2002 营业额统计

 

简单题,splay

题意:

  按顺序给出一些数,找出距离当前数最近的数的差,将这些差求和即可。

 

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3f#define MAXN 100005using namespace std;int cnt=1, rt=0;struct Tree{    int key, size, fa, son[2];    void set(int _key, int _size, int _fa)    {        key=_key;        size=_size;        fa=_fa;        son[0]=son[1]=0;    }}T[MAXN];inline void PushUp(int x){    T[x].size=T[T[x].son[0]].size+T[T[x].son[1]].size+1;}inline void Rotate(int x, int p) //0左旋 1右旋{    int y=T[x].fa;    T[y].son[!p]=T[x].son[p];    T[T[x].son[p]].fa=y;    T[x].fa=T[y].fa;    if(T[x].fa)        T[T[x].fa].son[T[T[x].fa].son[1] == y]=x;    T[x].son[p]=y;    T[y].fa=x;    PushUp(y);    PushUp(x);}void Splay(int x, int To) //将x节点插入到To的子节点中{    while(T[x].fa != To)    {        if(T[T[x].fa].fa == To)            Rotate(x, T[T[x].fa].son[0] == x);        else        {            int y=T[x].fa, z=T[y].fa;            int p=(T[z].son[0] == y);            if(T[y].son[p] == x)                Rotate(x, !p), Rotate(x, p); //之字旋            else                Rotate(y, p), Rotate(x, p);    //一字旋        }    }    if(To == 0) rt=x;}int find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处{    int x=rt;    while(x && T[x].key != key)        x=T[x].son[key > T[x].key];    if(x) Splay(x, 0);    return x;}int prev() //返回比根值小的最大值 若无返回0 若有将其转移到根处{    int x=T[rt].son[0];    if(!x) return 0;    while(T[x].son[1])        x=T[x].son[1];    //Splay(x, 0);    return x;}int succ() //返回比根值大的最小值 若无返回0 若有将其转移到根处{    int x=T[rt].son[1];    if(!x) return 0;    while(T[x].son[0])        x=T[x].son[0];    //Splay(x, 0);    return x;}void Insert(int key) //插入key 并且将该节点转移到根处{    if(!rt)        T[rt = cnt++].set(key, 1, 0);    else    {        int x=rt, y=0;        while(x)        {            y=x;            x=T[x].son[key > T[x].key];        }        T[x = cnt++].set(key, 1, y);        T[y].son[key > T[y].key]=x;        Splay(x, 0);    }}int getclose(int key){    if(!rt) return 0;    int x=rt, ret=2000000000;    while(x)    {        ret=min(ret, abs(T[x].key-key));        x=T[x].son[key > T[x].key];    }    return ret;}int main (){    int n, x, ans, mi;    scanf("%d%d", &n, &x);    Insert(x);    ans=x;    while(--n)    {        if(scanf("%d", &x)==EOF) x=0;        ans+=getclose(x);        Insert(x);    }    printf("%d\n", ans);    return 0;}
View Code

 

HNOI 2002 营业额统计