自动搬运

查看原文

来自洛谷，原作者为

	OrangeEye I half remember everything.

搬运于2025-08-24 22:24:49，当前版本为作者最后更新于2021-08-13 20:27:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

定义一种情况的中间最低的柱子为底柱。

设答案的底柱高为 $k$ 。

若有 $i \leq k$ ，则以 $i$ 为底柱的花费肯定比以 $i-1$为底柱的花费低。

证明：

设在一个位置上的目标高度是 $a$ ，Mirko 的初始高度是 $M$ ，Slavko 的初始高度是 $S$ ；

当 $a$减一时，若：

• $a \leq M$ 且 $a \leq S$ ，则总花费加2。

• $a \geq M$ 且 $a \geq S$ ，则总花费减2。

• 否则总花费不变。

由于 $k$ 为答案，则以 $k$ 为底柱的各个位置中，第一种情况的数量总是大于等于第二种情况的数量（否则以 $k-1$ 为底柱的花费比 $k$ 低）而在减一的过程中，第一种情况的数量只增不减，而第二种只减不增。所以减得越多，花费加得越多。

证毕。

同理，若有 $i \geq k$ ，则以 $i$ 为底柱的花费肯定比以 $i+1$ 为底柱的花费低。（读者自证不难）

所以，给定一个高度，可以知道它在答案的左边还是右边，考虑二分答案解决。

复杂度 $O(N\log_2\max(\max (m_i),\max (s_i)))$ 可过。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,a[300009],b[300009],n;
ll abs_(ll x){return (x>=0?x:-x);}
ll chk(ll t){
	ll ans=0;
	for(ll i=0;i<n;i++)ans+=abs_(t-a[i]+abs_(n/2-i));
	for(ll i=0;i<n;i++)ans+=abs_(t-b[i]+abs_(n/2-i));
	return ans;
}
void print(ll t){printf("%lld\n",chk(t));return ;}
int main(){
	scanf("%lld",&n);
	for(ll i=0;i<n;i++)scanf("%lld",a+i);
	for(ll i=0;i<n;i++)scanf("%lld",b+i);
	l=0ll;r=1000000000001ll;
	while(l<r){//二分
		ll mid=(l+r)/2;
		if(chk(mid+1)>chk(mid))r=mid;
		else l=mid+1;
	}
	print(l);
	return 0;
}