18.[HNOI2002]营业额统计

作者：H_D_NULL

---

本来想sort水过，看了一眼题解（呵呵呵），大佬们把能写的算法也都写了，但是本着学术精神，我觉得已发题解中Splay的写法太复杂（虽然快是快），所以在下提供一个将左旋右旋结合的写法。

Splay就不再赘述，翻翻前面大佬的题解就知道了

luogu说不能提交这道题的题解了,所以就写到这里吧

下面上代码

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

int ans,n,a;
map <int,int> vis;//懒人写法,导致程序变慢

struct Splay{
	int son[mn][2],fa[mn],v[mn],cnt,root;
    //son:左右儿子结点  fa:父结点  v:data  cnt:编号
	inline void rot(int x){
		int father=fa[x],gf=fa[father];//父亲和祖父……
		int s=(son[father][1]==x);//经典，判断是左儿子还是右儿子
		int sn=son[x][!s];//x对应位置上的儿子
		son[father][s]=sn;
		fa[sn]=father;
		son[fa[x]=gf][son[gf][1]==father]=x;
		son[fa[father]=x][!s]=father;
	}
	inline void splay(int x){
		while(fa[x]){
			if(fa[fa[x]]&&(son[fa[fa[x]]][1]==fa[x])==(son[fa[x]][1]==x)) rot(fa[x]);
            //如果其父结点有父结点且x一家三代(形象)共线,则先旋转x的父结点(不要问为什么)
			rot(x);
		}
		root=x;
	}
	int p,q;
	inline void find(int x){
		v[q=0]=x;p=root;
		while(v[p]!=x){ q=p;p=son[p][v[p]<x];}
	}
	inline void insert(int x){
		find(x);//找到x应插入的位置,及整棵树平衡
		v[++cnt]=x;
		fa[cnt]=q;
		son[q][v[q]<x]=cnt;
		splay(cnt);//旋转到根节点位置
	}
	inline void count(){
		int minn=1<<30;
		if(cnt<2){
			ans+=v[root];
			return;
		}
		int L=son[root][0];
        //从左儿子开始,找左子树最右结点,及有序集合中root的前驱
		while(L!=0){
			if(!son[L][1]) break;
			L=son[L][1];
		}
		if(L!=0) minn=min(minn,v[root]-v[L]);
		L=son[root][1];
        //找后继,因为root与前驱后继之差的绝对值最小
		while(L!=0){
			if(!son[L][0]) break;
			L=son[L][0];
		}
		if(L!=0) minn=min(minn,v[L]-v[root]);
		ans+=minn;
	}
}S;

int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		if(vis[a]) continue;
        //懒人写法,大佬们也可以不用STL,而在find中做文章
		vis[a]=1;
		S.insert(a);
		S.count();
	}
	printf("%d",ans);
	return 0;
} 
//P.S. 我不知道这个代码能不能过,伸手党注意

本文作者： 益题 Yitee
发布时间： 2020-12-13
最后更新： 2021-08-19
本文标题： 18.[HNOI2002]营业额统计
本文链接： https://yitee.top/posts/2629.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

微信