题解 P4523 【[COCI2017-2018 Contest4] Krov 】

x义x · 2019-11-11 20:32:12 · 题解

这题为什么黑啊……绿题差不多了吧……

首先这题是要选一个i和H_i使得

最小。

绝对值是很麻烦的东西，考虑拆掉。里面的那个|i-j|可以通过对i的左边右边分开考虑实现。于是和式变成：

这其实是一个很经典的问题：坐标轴上有一些点，求一个点到它们的距离和最小。众所周知这个选出的点就是所有点的中位数。

于是我们使用树状数组+二分查询中位数：查询左边满足X_j-j<H_i-i的j的数量，右边X_j+j<H_i+i的数量，如果这两个值加起来多于一半那么说明H_i估大了，否则估小了，于是可以二分。

查询答案则不难。以左边为例，对于X_j-j<H_i-i的j贡献是H_i-i-X_j+j，否则是其相反数，显然可以树状数组维护。

实现时还要注意一些小细节：

• 二分中位数时的“一半”应该是\lceil\frac n 2\rceil。

代码如下。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int inf=1000100000;

int N;
int X[100005],val[200005],n;
struct BIT{
    int C0[200005];ll C1[200005];
    void chn(int x,int k0,int k1){for(;x<=n;x+=x&-x) C0[x]+=k0,C1[x]+=k1;}
    int qst0(int x){int ans=0;for(;x;x-=x&-x) ans+=C0[x];return ans;}
    ll qst1(int x){ll ans=0;for(;x;x-=x&-x) ans+=C1[x];return ans;}
}Lbit,Rbit;
int Find(int x){
    int L=0,R=n,mid;
    while(L<R){
        mid=(L+R+1)>>1;
        if(val[mid]<=x) L=mid;
        else R=mid-1;
    }
    return L;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d",&X[i]),
        val[++n]=X[i]-i,val[++n]=X[i]+i;
    val[++n]=-inf;
    sort(val+1,val+n+1);n=unique(val+1,val+n+1)-val-1;

    for(int i=1;i<=N;i++) Rbit.chn(Find(X[i]+i),1,X[i]+i);

    ll ans=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=N;i++){
        Rbit.chn(Find(X[i]+i),-1,-X[i]-i);
        Lbit.chn(Find(X[i]-i),1,X[i]-i);

        int L=max(i,N-i+1),R=inf,mid;
        while(L<R){
            mid=(L+R)>>1;
            if(Lbit.qst0(Find(mid-i))+Rbit.qst0(Find(mid+i))>=(N+1)/2) R=mid;
            else L=mid+1;
        } 

        int cntLl=Lbit.qst0(Find(R-i)),cntLr=Lbit.qst0(Find(inf))-cntLl,
            cntRl=Rbit.qst0(Find(R+i)),cntRr=Rbit.qst0(Find(inf))-cntRl;
        ll  sumLl=Lbit.qst1(Find(R-i)),sumLr=Lbit.qst1(Find(inf))-sumLl,
            sumRl=Rbit.qst1(Find(R+i)),sumRr=Rbit.qst1(Find(inf))-sumRl;
        ans=min(ans,(sumLr-sumLl+1LL*(cntLl-cntLr)*(R-i))+(sumRr-sumRl+1LL*(cntRl-cntRr)*(R+i)));
    }
    printf("%lld\n",ans);
}