自动搬运

查看原文

来自洛谷，原作者为

	chenzhiyou12 *　*

搬运于2025-08-24 23:16:15，当前版本为作者最后更新于2025-05-18 21:25:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

赛时 lg 榜和正式榜独占（大概是？）。

可惜队友没有做出 FIM，遗憾 rk7。

下面给出一种比较简单易懂的做法（如有锅请大佬指正）。

首先，对于最终值取 $A,B,C$ 的情况，我们不难弄出一个人的最小操作次数，即 $cost(i)=\max({A-a_i,B-b_i,C-c_i,0})+\max({a_i-A,b_i-B,c_i-C,0})$。然后修改完所有的次数就是 $f(A,B,C)=\sum_{i=1}^{n}{cost(i)}$。

题意转化为求 $f(A,B,C)$ 的最小值。

不难发现，$f(A,B,C)$ 是分段凸函数，可以形象的理解为三位空间中一个表面粗糙的碗。

注意到 $A\in[\min(a_i),\max(a_i)],B\in[\min(b_i),\max(b_i)],C\in[\min(c_i),\max(c_i)]$。

按照直觉，我们可以先把 $A,B,C$ 分别取成 $a,b,c$ 三个数组的中位数，也就是让我们的起点尽量在“碗”靠内的位置。随后，因为 $f(A,B,C)$ 其实只在整点上有取值，所以我们可以不断地试图向 $27$ 个方向上的整点跳，根据凸性，如果跳出来的更优，那么我们就应该跳。

怎么决定跳多长的距离呢？可以直接倍增（准确来说是“倍减”），我们设 $k=max(\max(a_i)-\min(a_i),\max(b_i)-\min(b_i),\max(c_i)-\min(c_i))$（为了覆盖整个碗面），如果有一次跳成功了，我们就继续尝试跳，否则就将 $k$ 折半。还是因为只在整点取值，所以倍增一定能跳到最终最优的点（一定能凑出来整数）。

所以就有了代码：

#include<bits/stdc++.h>
#define ll long long
#define db double
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
#define For(i,j,k) for(int i=j;i<=k;++i)
#define Rof(i,j,k) for(int i=j;i>=k;--i)
using namespace std;
const int N=1e5+10,inf=0x3f3f3f3f;
int n;
vi a,b,c;
ll f(int A,int B,int C){
    ll ret=0;
    For(i,0,n-1){
        int d1=A-a[i],d2=B-b[i],d3=C-c[i];
        int v1=max({d1,d2,d3,0});
        int v2=max({-d1,-d2,-d3,0});
        ret+=v1+v2;
    }
    return ret;
}
int med(vi x){sort(x.begin(),x.end());return x[x.size()/2];}
int mn(vi x){
    int ret=inf;
    for(auto v:x){ret=min(ret,v);}
    return ret;
}
int mx(vi x){
    int ret=0;
    for(auto v:x){ret=max(ret,v);}
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    cin>>n;
    For(i,1,n){
        int na,nb,nc;cin>>na>>nb>>nc;
        a.pb(na),b.pb(nb),c.pb(nc);
    }
    int A=med(a),B=med(b),C=med(c);
    ll ans=f(A,B,C);
    int mna=mn(a),mxa=mx(a);
    int mnb=mn(b),mxb=mx(b);
    int mnc=mn(c),mxc=mx(c);
    int stp=max({mxa-mna,mxb-mnb,mxc-mnc});
    while(stp){
        bool flg=false;
        For(i,-1,1){For(j,-1,1){For(k,-1,1){
            int na=A+i*stp,nb=B+j*stp,nc=C+k*stp;ll now=f(na,nb,nc);
            if(now<ans){
                ans=now;
                A=na,B=nb,C=nc;
                flg=true;
            }
        }}}
        if(!flg){stp>>=1;}
    }
    cout<<ans<<'\n';
    return 0;
}

下面证明 $f(A,B,C)$ 的凸性。

首先我们知道，若 $f_1$ 和 $f_2$ 均为凸函数，$f_3=f_1+f_2$ 也是凸函数。

我们先证一个引理：

若 $g(x)=\max({f_1(x),f_2(x),\ldots,f_n(x)})$，其中 $f_1(x),f_2(x),\ldots,f_n(x)$ 均为仿射函数（形如 $f(x)=Ax+B$ 的函数），则 $g(x)$ 是凸函数。

证明：

可以先取两个向量 $x_1,x_2$ 和 $t\in[0,1]$。

有

整理就是：$g(tx_1+(1-t)x_2) \leq tg(x_1)+(1-t)g(x_2)$，符合凸函数的定义。

有了这个引理之后就好弄了。

$cost(i)=\max({A-a_i,B-b_i,C-c_i,0})+\max({a_i-A,b_i-B,c_i-C,0})$，不难发现，$A-a_i,B-b_i,C-c_i,0,a_i-A,b_i-B,c_i-C$ 都是仿射函数，所以 $\max({A-a_i,B-b_i,C-c_i,0})$ 和 $\max({a_i-A,b_i-B,c_i-C,0})$ 都是凸函数，所以 $cost(i)$ 是凸函数。

因为 $cost(i)$ 是凸函数，证得 $f(A,B,C)=\sum_{i=1}^{n}{cost(i)}$ 也是凸函数。