题解：P11558 [ROIR 2016 Day 2] 和谐数列

· · 题解

Solution

不难发现若一个和谐序列的前两项都确定了，则整个序列也都确定了。所以它一定是这样的形式：

u,v,v-u,-u,-v,u-v,\cdots

考虑设 f(u,v) 表示以 u,v 生成的和谐序列与 b 的距离，不难把 f(u,v) 表示成绝对值相加的形式。由于绝对值具有凸性，我们大胆猜测 f 也具有凸性，打个表发现对完了。

现在你只需要求 f 在 \mathbb Z\times \mathbb Z 上的最小值，二分一下斜率就做完了。复杂度 O(n\log n+\log^3 V)。

Code

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=3e5+5;
int n,a[N];
inline ll Abs(ll x){return x>0?x:-x;}
struct ds{
    int b[N],tot;ll s[N];
    inline void add(int x){b[++tot]=x;}
    void init(){
        sort(b+1,b+tot+1);
        for(int i=1;i<=n;i++)s[i]=s[i-1]+b[i];
    }
    inline ll qry(ll x){
        int pos=upper_bound(b+1,b+tot+1,x)-b-1;
        return (pos*x-s[pos])+(s[tot]-s[pos]-(tot-pos)*x);
    }
};
ds c[3];
inline ll f(ll u,ll v){
    return c[0].qry(u)+c[1].qry(v)+c[2].qry(v-u);
}
inline ll get(ll u){
    ll l=-1e10,r=1e10,mid;
    while(l<r){
        mid=(l+r+1)>>1;
        if(f(u,mid)-f(u,mid-1)<0)l=mid;
        else r=mid-1;
    }
    return f(u,l);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int k=0;k<3;k++){
        for(int i=k+1,op=1;i<=n;i+=3,op*=-1)
            c[k].add(a[i]*op);
        c[k].init();
    }
    ll l=-1e10,r=1e10,mid;
    while(l<r){
        mid=(l+r+1)>>1;
        if(get(mid)-get(mid-1)<0)l=mid;
        else r=mid-1;
    }
    cout<<get(l)<<'\n';
    return 0;
}