Mars_Cat

Description

Input

Output

Sample Input

Sample Output

HINT

题目数据有坑。。给你的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;
}