自动搬运

查看原文

来自洛谷，原作者为

	qczrz6v4nhp6u Tell me, what scares you.

搬运于2025-08-24 23:08:24，当前版本为作者最后更新于2025-01-10 21:28:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

不难发现若一个和谐序列的前两项都确定了，则整个序列也都确定了。所以它一定是这样的形式：

考虑设 $f(u,v)$ 表示以 $u,v$ 生成的和谐序列与 $b$ 的距离，不难把 $f(u,v)$ 表示成绝对值相加的形式。由于绝对值具有凸性，我们大胆猜测 $f$ 也具有凸性，打个表发现对完了。

现在你只需要求 $f$ 在 $\mathbb Z\times \mathbb Z$ 上的最小值，二分一下斜率就做完了。复杂度 $O(n\log n+\log^3 V)$。

Code

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=3e5+5;
int n,a[N];
inline ll Abs(ll x){return x>0?x:-x;}
struct ds{
	int b[N],tot;ll s[N];
	inline void add(int x){b[++tot]=x;}
	void init(){
		sort(b+1,b+tot+1);
		for(int i=1;i<=n;i++)s[i]=s[i-1]+b[i];
	}
	inline ll qry(ll x){
		int pos=upper_bound(b+1,b+tot+1,x)-b-1;
		return (pos*x-s[pos])+(s[tot]-s[pos]-(tot-pos)*x);
	}
};
ds c[3];
inline ll f(ll u,ll v){
	return c[0].qry(u)+c[1].qry(v)+c[2].qry(v-u);
}
inline ll get(ll u){
	ll l=-1e10,r=1e10,mid;
	while(l<r){
		mid=(l+r+1)>>1;
		if(f(u,mid)-f(u,mid-1)<0)l=mid;
		else r=mid-1;
	}
	return f(u,l);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int k=0;k<3;k++){
		for(int i=k+1,op=1;i<=n;i+=3,op*=-1)
			c[k].add(a[i]*op);
		c[k].init();
	}
	ll l=-1e10,r=1e10,mid;
	while(l<r){
		mid=(l+r+1)>>1;
		if(get(mid)-get(mid-1)<0)l=mid;
		else r=mid-1;
	}
	cout<<get(l)<<'\n';
	return 0;
}