自动搬运

查看原文

来自洛谷，原作者为

	北文 月光下转身

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

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

以下是正文

upd:8.29一个细节挂了被撤回了。
根据等腰三角形的性质，满足的序列一定只有一种数字，两种不同的数字。一种数字比较 trivial，下面只考虑两种数字的。设这两种数字分别为 $x,y$，不防钦定大小关系 $x<y$， 则还需要满足 $x+x>y$。

假设我们一开始就钦定最终的 $x,y$ ，那么需要的代价是

我们把数字全放在数轴上，这个式子的含义就是：在这个数轴上选取两个原点 (也就是上文中的$x,y$)，求和数轴上的点到这两个原点距离的较小值。
一个显然的想法是，一定能分成两部分，使得左半部分到达 $x$ 点更近，而右半部分到达 $y$ 更近。
我们枚举这个分界线，对于左边部分，显然是取到中位数的点最优，右半部分同理。
为什么要取中位数？学过初中的零点分段都知道....

如果满足 $x+x>y$ 则直接更新答案，但这样得出的 $x,y$ 并不一定满足 $x+x>y$ 的要求。

如果不满足，则我们需要 $x$ 向右调整，或者 $y$ 向左调整。 如果 $x$ 向右调整了 $k$ 格，那么 $y$ 能取到的范围可以确定，即

而由于越靠近中位数，所求式子越小，我们可以直接令

因此我们把调整后的代价看做一个函数 $f(k)$ ，通过人类智慧可以猜出他是单谷函数，因此可以用三分解决。
既然这是题解那我们还是需要证明一下的。
考虑设

$L(k),R(k)$ 分别表示左右部分的贡献。当我们将 $x$ 向右移动的时候， $x$ 左边的点会不断增多，也就是说 $L'(k)$ （ $L$ 函数的导函数，增量）是单调不减的。这里可能有一点难理解，你可以试着想想在一个数轴上移动 $x$，距离和的增量会不断变大。同理，$R(k)$ 函数类似 $L(k)$ 函数反过来，通过同样的分析可以得到 $R'(k)$ 也是单调不减的，因此原函数的导函数 $f'(k)=L'(k)+R'(k)$ 也是单调不减的，所以 $f(k)$ 是单谷函数。
直到这里，我们可以设计程序了。
1.枚举一个分割点，分成左部分和右部分。
2.求出两部分的中位数，看看是否合法。
3.若合法，直接更新答案，否则三分求出最小的点，再更新。
但这题还有一个 corner case，若最终变成的 $x,y$ 其中成为 $x$ 的只有一个数，则不需要 $x+x<y$ 的限制，特判掉即可。
有点省选联考 D1T1 的感觉。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5, inf=1e9;
using ll=long long;
int n, a[N];
ll ans=1ll*inf*inf, s[N];
ll calc(int l, int r, int x) {
	int f=upper_bound(a+l, a+r+1, x)-a-1;
	ll lp=f-l+1, rp=r-f;
	return (lp*x-(s[f]-s[l-1]))+(s[r]-s[f]-rp*x);
}
void solve(int mid, int x, int y) {
	int l=0, r=inf;
	while(l+20<=r) {
		int lp=l+(r-l)/3;
		int rp=lp+(r-l)/3;
		ll lans=(calc(1, mid, x+lp)+calc(mid+1, n, min(x+lp+x+lp-1, y))), 
		   rans=(calc(1, mid, x+rp)+calc(mid+1, n, min(x+rp+x+rp-1, y)));
		if(lans<rans) r=rp;
		else l=lp;
	}
	ll res=1ll*inf*inf;
	for(int i=l; i<=r; i++) {
		res=min(res, calc(1, mid, x+i)+calc(mid+1, n, min(x+i+x+i-1, y)));
	}
		
	ans=min(ans, res);
	return ;
}
int main() {
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
		scanf("%d", &a[i]);
	sort(a+1, a+1+n);
	for(int i=1; i<=n; i++)
		s[i]=s[i-1]+a[i];
	
	for(int i=1; i<n; i++) {
		int x=a[i/2+1], y=a[(n-i+1)/2+i];
		if(x+x>y) ans=min(ans, calc(1, i, x)+calc(i+1, n, y));
		else solve(i, x, y);
	}
	ans=min(ans, calc(2, n, a[1+(n-1)/2]));
	printf("%lld\n", ans);
	return 0;
}