P6874 题解

· · 题解

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

设答案的底柱高为 k 。

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

证明：

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

当 a减一时，若：

由于 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;
}