方法一：暴力枚举O(N^2×M^2)

据出题人分析：“简要题意是找到一个位置，使得其它所有位置上的数乘以两个位置之间的距离的总和最小。直接暴力枚举每一个位置然后取一个最小值即可。”

for (int x = 1; x <= n; x++)
   for (int y = 1;y <= m; y++){//枚举仓库的位置(x,y)
       sum = 0;
       for (int i = 1;i <= n; i++)
          for (int j = 1;j <= m; j++)
             sum += mp[i][j] * (abs(x - i) + abs(y - j));//计算与每一个地点的距离再乘上要去的次数，简单模拟题意即可
       ans = min(ans, sum);
   }

方法二：数学方法（O(NM)）

如果数据范围较大，方法一恐怕是过不了的。做过的同学可能会想到《算法竞赛进阶指南》0x05中的货仓选址，这一题是给出每个地点的坐标，每个地方只需去一次，求将货仓建在哪个坐标上到各点距离和最小，答案中货仓的坐标就是所有坐标中的中位数(所有数与中位数的绝对差之和最小。具体证明请看其题解，我也写了一篇哦qwq!，这里就不赘述了)

那么，我们可以用货仓选址中的中位数来解决这题吗？货仓选址与这一题很相似，但也有不同，有什么不同呢？

  • 每个地方可能去多次：
    我们想到，其实没必要按照题目中的一个地方去多次，可以改成多个地方，每个地方只去一次，这样就可做了
  • 二维坐标：
    想想能不能由一维的情况拓展到二维呢？其实也是可以的，我们先把每一行都看做一个整体，变成一维，再用中位数的方法找到最优行(即仓库选在这一行到其他行之间的距离和最小，其实就是选在这一行的仓库到其他行中地点的竖直距离和最小)；然后再把每一列都看做一个整体做一遍，得到最优列(即仓库选在这一列到其他列之间的距离和最小，也就是选在这一列的仓库到其他列中地点的水平距离和最小)，那么最终仓库在哪最优呢？当然是最优行与最优列的交点洛！

当然数学方法可能不太好理解，可以看看下面的方法三

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int s[110][2],x[110],y[110],ans[2],sum;
inline void get_pos(int num,int lim) {//求中位数到底位于哪一行或那一列，当然你不用二分直接扫一遍s数组判断也可以
    int l=1,r=lim;
    while(l<=r) {
        int mid=(l+r)/2;
        if (s[mid][num]<sum/2) l=mid+1;//sum/2，中位数，也就是最优的位置
        else r=mid-1,ans[num]=mid;//返回最优行最优列的位置
    }
}
int main() {
    int T,n,m,_ans;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&m,&n),sum=_ans=0;
        memset(x,0,sizeof x);
        memset(y,0,sizeof y);
        for (int i=1,a; i<=n; i++)
            for (int j=1; j<=m; j++) {
                scanf("%d",&a),sum+=a;//sum统计一共有多少个地方，实际上把一个地方去a次，改成了a个地方，每个地方只去一次
                x[i]+=a,y[j]+=a;//x,y分别统计每行、每列的数字和，即把每行、每列看为一个整体
            }
        for (int i=1; i<=n; i++) s[i][0]=s[i-1][0]+x[i];
        for (int i=1; i<=m; i++) s[i][1]=s[i-1][1]+y[i];//前缀和
        get_pos(0,n),get_pos(1,m);//找最优行与最优列
        for (int i=1; i<=n; i++) _ans+=abs(ans[0]-i)*x[i];//计算所有竖直距离
        for (int i=1; i<=m; i++) _ans+=abs(ans[1]-i)*y[i];//计算所有水平距离
        //当然这个计算答案用二维的(abs(x - i) + abs(y - j))也可以
        printf("%d\n",_ans);
    }
}

方法三：二维前缀和（O(NM)）

这个算法可能比较简单易懂，二维前缀和的实现与计算就不再赘述了，可以上网查一下qwq

在暴力方法一中每次枚举一个坐标都要把到所有点的距离重新算一遍，其实没必要。

若仓库在点 (x,y) 处，现在将仓库移动到点 (x+1,y) ，那么对于左上角为(1,1)，右下角为(x,m)的矩阵，所有点到达仓库的距离都+1，对于左上角为(x+1,1)，右下角为(n,m)的矩阵，所有点到达仓库的距离都-1。若仓库在点 (x,y) 处，现在将仓库移动到点 (x,y+1)同理计算即可。

#include<cstdio>
using namespace std;
#define min(a,b) (a<b ? a:b)
int a[110][110],s[110][110];
inline int calc(int A,int B,int C,int D) {
    return s[C][D]-s[A-1][D]-s[C][B-1]+s[A-1][B-1];//计算左上角为(A,B),右下角为(C,D)的矩形中数的总和
}
int main() {
    int T,n,m,now,nxt,ans;
    scanf("%d",&T);
    while(T--) {
        now=nxt=0,ans=0x3f3f3f3f;
        scanf("%d%d",&m,&n);
        for (int i=1,x; i<=n; i++)
            for (int j=1; j<=m; j++)
                scanf("%d",&x),now+=(i-1+j-1)*x,//now计算开始位置(1,1)时到所有点的距离和
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;//二维前缀和
        for (int i=1; i<=n; i++) {
            nxt=now;
            for (int j=1; j<=m; j++) {
                ans=min(ans,nxt);
                nxt+=calc(1,1,n,j)-calc(1,j+1,n,m);// (x,y)移动到(x,y+1)
            }
            now+=calc(1,1,i,m)-calc(i+1,1,n,m);// (x,y)移动到(x+1,y) 
        }
        printf("%d\n",ans);
    }
}

欢迎各位dalao提出改进和建议qwq！