自动搬运

查看原文

来自洛谷，原作者为

	Mirasycle 遗憾离场

搬运于2025-08-24 23:16:02，当前版本为作者最后更新于2025-06-07 23:27:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

不错的函数最优化练习题。考验选手卡常技巧。

首先，对于一个选手来说向左走和向右走是独立的。有两种策略，一个是向左来回走一趟然后向右，另一种是向右来回一趟再向左。直接把来回的权值设成 $2w$ 即可。然后两种策略的答案取 $\min$ 即可。

于是经过上述转化，我们只需要平移坐标然后考虑从 $x_0=0$ 开始的单方向行走就行了。一个最直接的策略就是枚举走到了哪个位置 $x$，有一个行走的能量，$w\times x$，已经被覆盖的点 $c_i$ 消耗的能量就是 $\min((c_i\bmod d)^2,(c_i-c_i\bmod d)^2)$，未被覆盖点消耗的能量是 $(c_i-x)^2$。于是答案就是

$$f(x)=w\times x+\sum\limits_{c_i\le x} \min((c_i\bmod d)^2,(c_i-c_i\bmod d)^2)+\sum\limits_{c_i>x}(c_i-x)^2 $$

记录一些前后缀和可以 $O(\log n)$ 计算这个式子，带 $\log$ 的原因是你需要二分出 $c_i\le x$ 的分界点 $i$。

这个式子是一些二次函数状物构成的，所以我们猜测其具有凸性，且是一个单谷函数。

于是可以通过直接三分来找到极值点，单次计算 $f(x)$ 的代价为 $O(n\log n)$。所以总的时间复杂度就是 $O(m\log n\log V)$，可以喜提 $87\rm pts$。

发现复杂度的瓶颈是在于每次三分内部要要二分出是在哪一段。于是我们可以先三分出在哪一段，然后段内再三分出哪个是极值点，这样子第一次计算的时候取点我们直接取段内的左右端点即可，第二次计算的时候已经确定段了就不需要再二分段了。时间复杂度也可以做到 $O(m(\log n+\log V))$，可以获得 $91 \rm pts$。

不过其实最后确定段之后，其中一个变量分界点 $i$ 已经确定了，于是这就是一个纯的二次函数，我们可以直接求出二次函数极值点，然后在附近找到 $d$ 的倍数看看谁最优即可（注意特判二次项系数为 $0$）。于是又优化掉一个 $\log V$。时间复杂度 $O(m\log n)$，还是 $91\rm pts$。

其实整数域的三分是可以用二分替代的，因为下凸函数满足差分单调递增，我们直接二分出差分值在 $0$ 附近的点即可。这样子能大幅度减少常数，获得 $100 \rm pts$。

当然由于我的写法比较丑陋，所以还需要加入下面若干常数优化。

• 可以发现随着 $w$ 的增大，我们的最优行走距离 $x$ 是单调递减的，所以我们可以对于询问的 $w$ 进行排序，然后每次就可以缩短二分上界了。

• 虽然是 $O(1)$ 计算函数值，但是由于计算过程中涉及 __int128，所以下面代码中的 $g$ 函数的计算会异常地慢，可以发现由于 $g$ 是段的函数值，一共只有 $O(n)$ 段，我们可以提前算出这些值，然后直接用即可。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef __int128 i128;
const int maxn=3e5+10;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct Calc{
	int c[maxn],to[maxn],p[maxn],n,m,d,W,R,lst[3];
	i128 pre[maxn],s1[maxn],s2[maxn],v1[maxn],v2[maxn]; int id;
	ll V(ll x){ return x*x; }
	inline i128 f(ll x){ return W*x/d+pre[id]+s2[id+1]-2*x*s1[id+1]+(i128)(n-id)*x*x; }
	inline i128 g(int z){
		ll x1=p[z],x2=p[z+1]-d;
		if(x1==x2) return W*x1/d+v1[z];
		return min(W*x1/d+v1[z],W*x2/d+v2[z]);
	}
	inline void G(int z){
		ll x1=p[z],x2=p[z+1]-d;
		v1[z]=pre[to[z]]+s2[to[z]+1]-2*x1*s1[to[z]+1]+(i128)(n-to[z])*x1*x1;
		v2[z]=pre[to[z]]+s2[to[z]+1]-2*x2*s1[to[z]+1]+(i128)(n-to[z])*x2*x2;
	}
	void init(){
		sort(c+1,c+1+n); m=0; c[n+1]=2e9;
		if(c[1]){ p[++m]=0; to[m]=0; }// p:坐标 to:覆盖了前缀哪些位置 
		for(int i=1;i<=n;i++){
			int z=c[i]%d==0?c[i]:c[i]+d-c[i]%d;
			if(z<c[i+1]) p[++m]=z,to[m]=i;
			pre[i]=pre[i-1]+V(min(c[i]%d,d-c[i]%d));
		} 
		p[m+1]=p[m]+d; lst[1]=lst[2]=m-1;
		for(int i=n;i>=1;i--) s1[i]=s1[i+1]+c[i],s2[i]=s2[i+1]+V(c[i]);
		for(int i=1;i<=m;i++) G(i);
	}
	ll calc(int w,int t){
		if(m==1) return 0; 
		W=w; int l=1,r=min(lst[t],m-1);
		while(l<r){
			int mid=(l+r)>>1;
			if(g(mid)-g(mid+1)<=0) r=mid;
			else l=mid+1;
		}
		int id2=g(l)<g(l+1)?l:l+1; lst[t]=id2; 
		l=p[id2]; r=p[id2+1]-d; id=to[id2];
		i128 ans=min(f(l),f(r));
		if(n!=id){
			i128 x1=(2*d*s1[id+1]-W)/2/d/(n-id);
			ll v1=x1+d-x1%d,v2=x1-x1%d;
			if(l<=v1&&v1<=r) ans=min(ans,f(v1));
			if(l<=v2&&v2<=r) ans=min(ans,f(v2));
		}
		return (ll)ans;
	}
}L,R;
int n,m,a[maxn],x0; ll ans[maxn<<1];
vector<pair<int,int> > Q;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) a[i]=read();
	cin>>x0>>L.d; R.d=L.d;
	for(int i=1;i<=n;i++)
		if(a[i]<=x0) L.c[++L.n]=x0-a[i];
		else R.c[++R.n]=a[i]-x0;
	cin>>m; L.init(); R.init();
	for(int i=1;i<=m;i++) Q.pb(read(),i);
	sort(Q.begin(),Q.end());
	for(auto z:Q) ans[z.se]=min(L.calc(z.fi,1)+R.calc(2*z.fi,2),L.calc(2*z.fi,2)+R.calc(z.fi,1));
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}