题解:P12532 [XJTUPC 2025] Primal Core Optimization: Attribute Balance

· · 题解

赛时 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_1f_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_2t\in[0,1]

g(tx_1+(1-t)x_2)=\max f(tx_1+(1-t)x_2) =\max [tf(x_1)+(1-t)f(x_2)] \leq t(\max f(x_1))+(1-t)(\max f(x_2)) =tg(x_1)+(1-t)g(x_2)

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

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

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