3
13
2016
0

BZOJ 1588: [HNOI2002]营业额统计 && AVL树板子

Time Limit: 5 Sec  Memory Limit: 162 MB

Description

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

Input

第一行为正整数 ,表示该公司从成立一直到现在的天数,接下来的n行每行有一个整数(有可能有负数) ,表示第i天公司的营业额。

Output

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

Sample Input

6
5
1
2
5
4
6

Sample Output

12

HINT

 

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

题目数据有坑。。给你的n不一定是之后输入的数的数量。。如果他给的数不够你需要用0补足。

然后呢 就学习了奇怪的树 有了AVL树的模板。。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
struct node
{
	int v;
	int ls,rs; 
	int l,r;
	int fa;
}T[100010];
int tot=1;
int G,x;
int ans=0;

inline int Ask(int w,int x)
{
	if(x==T[w].v)return 0;
	if(x>T[w].v)
	{
		if(T[w].rs!=-1)return min(x-T[w].v,Ask(T[w].rs,x));
		else return x-T[w].v;
	}
	else 
	{
		if(T[w].ls!=-1)return min(T[w].v-x,Ask(T[w].ls,x));
		else return T[w].v-x;
	}
}

inline void Shift_R(int w)
{
	if(T[w].fa==G)G=w;
	T[T[w].fa].ls=T[w].rs;
	if(T[w].rs!=-1)T[T[w].rs].fa=T[w].fa;
	T[w].rs=T[w].fa;
	
	T[T[w].fa].l=T[w].r;
	T[w].r=max(T[T[w].rs].l,T[T[w].rs].r)+1;
	
	int tmp=T[T[w].fa].fa;
	T[T[w].fa].fa=w;
	T[w].fa=tmp;
	if(T[tmp].ls==T[w].rs)T[tmp].ls=w;else T[tmp].rs=w;
}

inline void Shift_L(int w)
{
	if(T[w].fa==G)G=w;
	T[T[w].fa].rs=T[w].ls;
	if(T[w].ls!=-1)T[T[w].ls].fa=T[w].fa;
	T[w].ls=T[w].fa;
	
	T[T[w].fa].r=T[w].l;
	T[w].l=max(T[T[w].ls].r,T[T[w].ls].l)+1;
	
	int tmp=T[T[w].fa].fa;
	T[T[w].fa].fa=w;
	T[w].fa=tmp;
	if(T[tmp].ls==T[w].ls)T[tmp].ls=w;else T[tmp].rs=w;
}

inline void Ins(int w,int x)
{
	if(x==T[w].v)return; 
	if(x>T[w].v)
	{
		if(T[w].rs==-1)
		{
			T[w].rs=++tot;
			T[tot].ls=T[tot].rs=-1; T[tot].l=T[tot].r=0; T[tot].v=x; T[tot].fa=w;
			T[w].r=1;
		}
		else 
		{
			Ins(T[w].rs,x);
			T[w].r=max(T[T[w].rs].l,T[T[w].rs].r)+1;
		}
	}
	else 
	{
		if(T[w].ls==-1)
		{
			T[w].ls=++tot;
			T[tot].ls=T[tot].rs=-1; T[tot].l=T[tot].r=0; T[tot].v=x; T[tot].fa=w;
			T[w].l=1;
		}
		else 
		{
			Ins(T[w].ls,x);
			T[w].l=max(T[T[w].ls].l,T[T[w].ls].r)+1;
		}
	}
	if(T[w].l-T[w].r>1)
	{
		if(T[T[w].ls].l-T[T[w].ls].r<0)Shift_L(T[T[w].ls].rs);
		Shift_R(T[w].ls);
	}
	else 
	if(T[w].r-T[w].l>1)
	{
		if(T[T[w].rs].r-T[T[w].rs].l<0)Shift_R(T[T[w].rs].ls);
		Shift_L(T[w].rs);
	}
}

int main()
{
	scanf("%d%d",&n,&x);
	--n;
	ans+=x;
	G=1; T[tot].ls=T[tot].rs=-1; T[tot].l=T[tot].r=0; T[tot].v=x; T[tot].fa=0;
	while(scanf("%d",&x)!=EOF)
	{
		--n;
		ans+=Ask(G,x);
		Ins(G,x);
	}
	while(n--){ans+=Ask(G,0);Ins(G,0);}
	printf("%d\n",ans);
	return 0;
}

之前做的时候还有暴力乱搞做法发现是可以过的= =|排序之后向两边无脑暴力搜索= =|woc出数据的卡不平衡的二叉查找树也不卡暴力?!

 

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;
#define INF 0x7fffffff
int n;
long long ans=0;
struct node{long long x;int w;}a[100010];
bool cmp(node xx,node yy)
{
	return xx.x<yy.x;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lld",&a[i].x),a[i].w=i;
	sort(a+1,a+1+n,cmp);
	a[0].x=INF; a[0].w=0; 
	a[n+1].x=-INF; a[n+1].w=0; 
	for(int i=1;i<=n;++i)
	{
		if(a[i].w==1)
		{
			ans+=a[i].x;
			continue;
		}
		int l=i,r=i;
		while(a[l].w>=a[i].w)--l;
		while(a[r].w>=a[i].w)++r;
		ans+=min(abs(a[r].x-a[i].x),abs(a[i].x-a[l].x));
	}
	printf("%lld\n",ans);
	return 0;
}

 

Category: 程序 | Tags: AVL树 BZOJ | Read Count: 208

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com