贪心、博弈论

将点 $i$ 和点 $j$ 在所有维度的距离和 $\sum dis_{i,j}$ 视为边 $(i,j)$ 的边权，把边权同时加到两个节点的贡献里。

如果节点 $i,j$ 被同一个人选择，这个人会获得双倍边权；如果没有，两个人的收益之差不会受到影响，所以对答案也没有影响。

容易确定贪心策略为优先选择贡献大的节点，算出每个节点的贡献之后就可以开始选择。计算节点贡献时 $k$ 个维度是独立的，排序后拆绝对值可以完成对一个维度的贡献计算。

注意答案要在完成累加之后除以二，直接把每个点的贡献除以二会导致点贡献下取整，计算出错。

时间复杂度 $O(nk \log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,k,*a[200'005],p[200'005];
long long ans,sum[200'005];
void calculate(int x){
    long long pre=0ll,suf=0ll;
    for(int i=1;i<=n;i++) suf+=a[i][x];
    for(int i=1;i<=n;i++){
        sum[p[i]]+=1ll*(i-1)*a[p[i]][x]-pre;
        pre+=a[p[i]][x],suf-=a[p[i]][x];
        sum[p[i]]+=suf-1ll*(n-i)*a[p[i]][x];
    }
}
int main(){
    scanf("%d%d",&n,&k);
    n<<=1,iota(p+1,p+n+1,1);
    for(int i=1;i<=n;i++){
        a[i]=new int[k+5];
        for(int j=1;j<=k;j++) scanf("%d",&a[i][j]);
    }
    for(int i=1;i<=k;i++){
        sort(p+1,p+n+1,[&](auto x,auto y){return a[x][i]<a[y][i];});
        calculate(i);
    }
    sort(sum+1,sum+n+1,greater<long long>());
    for(int i=1;i<=n;i++){
        if(i&1) ans+=sum[i];
        else ans-=sum[i];
    }
    ans>>=1;
    printf("%lld\n",ans);
    return 0;
}