2021.08.01 P4311 数字序列（左偏树）

[P4331 BalticOI 2004]Sequence 数字序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.对于左偏树的应用

2.好好复习一下高中数学必修三

题意：

给定一个整数序列a_1, a_2, ··· , a_n，求出一个递增序列b_1 < b_2 < ··· < b_n，使得序列a_i和b_i的各项之差的绝对值之和|a_1 - b_1| + |a_2 - b_2| + ··· + |a_n - b_n|最小。

分析：

当求一个数x，使得a[1],a[2]…,a[n]最小，这个数为这n个数的中位数。

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=1e6+10;

typedef long long ll;

int n,top,array[N],ansi[N],vis[N],fa[N];

ll ans;

struct node{

	ll val;

	int rs,ls,rt,size;

}ai[N];

struct nodei{

	ll val;

	int ls,rs,dis;

}a[N];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

int find(int x){

	return fa[x]==x?x:fa[x]=find(fa[x]);

}

int merge(int x,int y){

	if(!x||!y)return x+y;

	if(array[x]==array[y]?x>y:array[x]<array[y])swap(x,y);

	//既然要求递增，那肯定是大根堆

	//而且要求在尽可能早的位置元素尽可能的小，如果合并，肯定从后开始删除对顶元素

	a[x].rs=merge(a[x].rs,y);

	if(a[a[x].ls].dis<a[a[x].rs].dis)swap(a[x].ls,a[x].rs);

	fa[x]=fa[a[x].ls]=fa[a[x].rs]=x;

	a[x].dis=a[a[x].rs].dis+1;

	return x;

}

void pop(int x){

	vis[x]=1;

	fa[a[x].ls]=a[x].ls;fa[a[x].rs]=a[x].rs;

	fa[x]=merge(a[x].ls,a[x].rs);

	a[x].ls=a[x].rs=a[x].dis=0;

}

int main(){

	n=read();

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

		a[i].val=array[i]=read()-i;fa[i]=i;

		//ansi[i]=1;

	}

	a[0].dis=-1;

	/*for(int i=1;i<n;i++){

		int x=find(i);

		fa[x]=merge(x,i+1);

	}

	for(int i=1;i<=n;i++)

	cout<<i<<" ls "<<a[i].ls<<" rs "<<a[i].rs<<" val "<<a[i].val<<" id "<<a[i].id<<" dis "<<a[i].dis<<endl;

	cout<<endl;*/

	//每一个x位置的最小值是包含i的这一堆中的最小值

	// 尝试找最长上升子序列

	/*for(int i=1;i<=n;i++){

		for(int j=1;j<i;j++)if(ai[j]<ai[i])ansi[i]=max(ansi[i],ansi[j]+1);

	}

	for(int i=1;i<=n;i++)cout<<ansi[i]<<" ";

	cout<<endl<<endl;*/

	//没用

	//运用中位数知识，中位数必须递增，否则和前一个小区间合并

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

		++top;

		ai[top].ls=ai[top].rs=ai[top].rt=i;ai[top].size=1;

		ai[top].val=array[i];

		while(top>1&&ai[top].val<ai[top-1].val){

            //合并区间

			--top;

			ai[top].rt=merge(ai[top].rt,ai[top+1].rt);

			ai[top].size+=ai[top+1].size;

			ai[top].rs=ai[top+1].rs;

			while(ai[top].size*2>ai[top].rs-ai[top].ls+2){//严格的中位数

			//size>(rs-ls+1)/2->size*2>rs-ls+1

			//当rs-ls+1为偶数时，取偏后的数为中位数

			//当rs-ls+1为奇数时，向上取整

				--ai[top].size;

				ai[top].rt=merge(a[ai[top].rt].ls,a[ai[top].rt].rs);

				//简易版pop：不断删去堆顶的中位数

			}

			ai[top].val=array[ai[top].rt];

		}

		/*for(int j=1;j<=n;j++)

		cout<<j<<" ls "<<a[j].ls<<" rs "<<a[j].rs<<" dis "<<a[j].dis<<" val "<<a[j].val<<endl;

		cout<<endl<<endl;*/

	}

	/*for(int i=1;i<=top;i++)

	cout<<i<<" ls "<<ai[i].ls<<" rs "<<ai[i].rs<<" rt "<<ai[i].rt<<" val "<<ai[i].val<<endl;

	cout<<endl;*/

	for(int i=1;i<=top;i++)for(int j=ai[i].ls;j<=ai[i].rs;j++){

		ansi[j]=ai[i].val;

		ans+=abs(ai[i].val-array[j]);

	}

	cout<<ans<<endl;

	for(int i=1;i<=n;i++)cout<<ansi[i]+i<<" ";

	return 0;

}

巴特西

2021.08.01 P4311 数字序列（左偏树）

2021.08.01 P4311 数字序列（左偏树）

最新文章

热门文章