BZOJ1367：[Baltic2004]sequence

浅谈左偏树：https://www.cnblogs.com/AKMer/p/10246635.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=1367

显然，如果给出的数组是递增的，那么答案就是\(0\)。

如果给出的数组是递减的，根据贪心的思想答案就是\(\sum\limits_{i=1}^{n}|x-t_i|\)，\(x\)是\(t\)数组的中位数。

但是给出的数组是无序的。

我们可以把这个数组划成一段段的，每一段都选一个\(x\)去当做中位数。简单的来讲，最优的方案是\(z_i=t_i\)的，但是为了保证\(z\)数组的递增性我们必须要把比前一位小的\(z\)和前一位合并到一段里去，形成新的一段，然后这一段的\(z\)就是这一段\(t\)的中位数。

但是这样出现了重复的\(z\)，不满足严格递增的性质。但是我们只需要把\(t_i=t_i-i\)就行了。这样就默认是严格递增的了。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=1e6+5;

ll ans;

int n,tot,cnt;

int l[maxn],r[maxn];

int fa[maxn],dist[maxn],son[maxn][2];

int a[maxn],rt[maxn],val[maxn],siz[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

int newnode(int v) {

	val[++tot]=v;

	siz[tot]=1;return tot;

}

int merge(int a,int b) {

	if(!a||!b)return a+b;

	if(val[a]<val[b])swap(a,b);

	son[a][1]=merge(son[a][1],b);

	if(dist[son[a][1]]>dist[son[a][0]])

		swap(son[a][1],son[a][0]);

	dist[a]=dist[son[a][1]]+1;

	siz[a]=siz[son[a][0]]+1+siz[son[a][1]];

	return a;

}

int pop(int u) {

	int res=merge(son[u][0],son[u][1]);

	son[u][0]=son[u][1]=0;

	return res;

}

int main() {

	n=read(),dist[0]=-1;

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

		a[i]=read()-i;

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

		rt[++cnt]=newnode(a[i]);l[cnt]=r[cnt]=i;

		while(cnt>1&&val[rt[cnt]]<val[rt[cnt-1]]) {

			rt[cnt-1]=merge(rt[cnt-1],rt[cnt]);r[--cnt]=i;

			while(siz[rt[cnt]]>(r[cnt]-l[cnt]+2)/2)rt[cnt]=pop(rt[cnt]);

		}

	}

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

		for(int j=l[i];j<=r[i];j++)

			ans+=abs(val[rt[i]]-a[j]);

	printf("%lld\n",ans);

	return 0;

}

巴特西

BZOJ1367：[Baltic2004]sequence

最新文章

热门文章