[BZOJ1588]营业额统计（Splay）

Description

题意：给定 n个数，每给定一个数，在之前的数里找一个与当前数相差最小的数，求相差之和（第一个数为它本身）

如：5 1 2 5 4 6

Ans=5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

n<=32767

Solution

平衡树入门题，每读入一个数，将当前数旋转至树根，在左子树中找一个最大以及右子树中最小的与根进行比较即可

Code

#include <cstdio>

#include <algorithm>

#define N 33333

#define Inf 0x7fffffff/2//会爆int

#define lc(x) ch[(x)][0]

using namespace std;

int n,root,tmp,fa[N],ch[N][2],k[N],ind=1,Ans;

//k[]下标节点储存的值

inline void rotate(int p){//旋转

	int q=fa[p],y=fa[q],x=(ch[q][1]==p);

	ch[q][x]=ch[p][x^1];fa[ch[q][x]]=q;

	ch[p][x^1]=q;fa[q]=p;

	fa[p]=y;

	if(y){

		if(ch[y][0]==q) ch[y][0]=p;

		else if(ch[y][1]==q) ch[y][1]=p;

	}

}

inline void splay(int x){

	for(int y;y=fa[x];rotate(x))

		if(fa[y]) rotate((x==lc(y))==(y==lc(fa[y]))?y:x);

	root=x;

}

inline void Ins(int x,int v){//插入

	int y;

	while(1){

		y=ch[x][k[x]<v];

		if(!y){//当前节点为空即储存

			y=++ind;

			k[y]=v;

			ch[y][0]=ch[y][1]=0;

			fa[y]=x;

			ch[x][k[x]<v]=y;

			break;

		}

		x=y;

	}

	splay(y);

}

inline int Min(int x){

	int t=ch[x][0];

	while(ch[t][1]) t=ch[t][1];

	return k[t];

}

inline int Max(int x){

	int t=ch[x][1];

	while(ch[t][0]) t=ch[t][0];

	return k[t];

}

int main(){

	scanf("%d%d",&n,&tmp);

	k[root=1]=Ans=tmp;

	Ins(root,Inf),Ins(root,-Inf);//初始化

	for(int i=2;i<=n;++i){

		scanf("%d",&tmp);

		Ins(root,tmp);

		int mi=Min(root),mx=Max(root);

		Ans+=min(tmp-mi,mx-tmp);

	}

	printf("%d\n",Ans);

	return 0;

}

巴特西

[BZOJ1588]营业额统计（Splay）

Description

Solution

Code

最新文章

热门文章