题解:P12532 [XJTUPC 2025] Primal Core Optimization: Attribute Balance
chenzhiyou12 · · 题解
赛时 lg 榜和正式榜独占(大概是?)。
可惜队友没有做出 FIM,遗憾 rk7。
下面给出一种比较简单易懂的做法(如有锅请大佬指正)。
首先,对于最终值取
题意转化为求
不难发现,
注意到
按照直觉,我们可以先把
怎么决定跳多长的距离呢?可以直接倍增(准确来说是“倍减”),我们设
所以就有了代码:
#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;
}
下面证明
首先我们知道,若
我们先证一个引理:
若
证明:
可以先取两个向量
有
整理就是:
有了这个引理之后就好弄了。