链接：https://ac.nowcoder.com/acm/contest/4462/G
来源：牛客网
时间限制：C/C++ 4秒，其他语言8秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
牛能在某小城有了固定的需求，为了节省送货的费用，他决定在小城里建一个仓库，但是他不知道选在哪里，可以使得花费最小。
给出一个m×n的矩阵，代表下一年小城里各个位置对货物的需求次数。我们定义花费为货车载货运输的距离，货车只能沿着水平或竖直方向行驶。
输入描述:
首先在一行中输入T,T≤10，代表测试数据的组数。
每组输入在第一行给出两个正整数n,m,1≤n,m≤100，分别代表矩阵的宽和高。
接下来m行，每行n个不超过1000的数字，代表矩阵里的元素。
输出描述:
每组输入在一行中输出答案。
输入
3 2 2 1 1 1 0 4 4 0 8 2 0 1 4 5 0 0 1 0 1 3 9 2 0 6 7 0 0 0 0 0 0 0 1 0 3 0 1 2 9 1 2 1 2 8 7 1 3 4 3 1 0 2 2 7 7 0 1 0 0 1 0 0 0 0 0 0 0
输出
2 55 162
备注:
送货时只能单次运输，若该位置需要3次，货车必须跑3次。
即使该位置需要被送货，我们仍然可以选择该位置作为仓库。
题意是找到一个位置，使得其它所有位置上的数乘以两个位置之间的距离的总和最小。
由于时间给4s，所以直接暴力枚举每一个位置然后取一个最小值即可，最后耗时约2000ms。
1 #include <bits/stdc++.h> 2 typedef long long LL; 3 const int INF=0x3f3f3f3f; 4 const double eps =1e-8; 5 const int mod=1e9+7; 6 const int maxn=1e5+10; 7 using namespace std; 8 9 10 int G[105][105]; 11 12 int main() 13 { 14 #ifdef DEBUG 15 freopen("sample.txt","r",stdin); 16 #endif 17 18 int T; 19 scanf("%d",&T); 20 while(T--) 21 { 22 int n,m; 23 scanf("%d %d",&m,&n); 24 for(int i=1;i<=n;i++) 25 { 26 for(int j=1;j<=m;j++) 27 scanf("%d",&G[i][j]); 28 } 29 int ans=INF; 30 for(int x=1;x<=n;x++) 31 { 32 for(int y=1;y<=m;y++) 33 { 34 int sum=0; 35 for(int i=1;i<=n;i++) 36 { 37 for(int j=1;j<=m;j++) 38 { 39 sum+=G[i][j]*(abs(x-i)+abs(y-j)); 40 } 41 } 42 ans=min(ans,sum); 43 } 44 } 45 printf("%d ",ans); 46 } 47 48 return 0; 49 }
但是，暴力太对不起这题了，故我们用二维前缀和来重写这题，最后耗时约20ms。
我们首先暴力处理出仓库在(1, 1)花费sum，再利用二维前缀和处理运输次数ci[i][j]，然后枚举每一位置的花费。
假设仓库当前在(x, y)，当仓库移动到(x, y+1)时，那么从(1, 1)到（n, y）的子矩阵移动距离+1，从(1, y+1)到(n, m)的子矩阵移动距离-1。所以从(1, 1)到（n, y）的矩阵区域内一共要运输多少次，总花费就加多少，因为每次运输的距离都要+1,而从(1, y+1)到(n, m)的矩阵区域内一共要运输多少次，总花费就减多少，因此可以由(x, y)的花费求出(x, y+1)的花费
同样考虑(x, y)移动到(x+1, y)的情况，从(1, 1)到（x, m）的子矩阵移动距离+1，从(x+1, 1)到(n, m)的子矩阵移动距离-1。
根据代码和注释理解吧：
1 #include <bits/stdc++.h> 2 typedef long long LL; 3 const int INF=0x3f3f3f3f; 4 const double eps =1e-8; 5 const int mod=1e9+7; 6 const int maxn=1e5+10; 7 using namespace std; 8 9 int ci[105][105];//二维前缀和求出(1,1)到(i,j)的运输次数和 10 11 int cal(int x1,int y1,int x2,int y2)//计算从左上角(x1, y1)到右下角(x2, y2)矩阵区域的运输次数和 12 { 13 return ci[x2][y2]-ci[x1-1][y2]-ci[x2][y1-1]+ci[x1-1][y1-1]; 14 } 15 16 int main() 17 { 18 #ifdef DEBUG 19 freopen("sample.txt","r",stdin); 20 #endif 21 22 int T; 23 scanf("%d",&T); 24 while(T--) 25 { 26 int n,m; 27 scanf("%d %d",&m,&n); 28 int sum=0; 29 for(int i=1;i<=n;i++) 30 { 31 for(int j=1;j<=m;j++) 32 { 33 int x; 34 scanf("%d",&x); 35 sum+=x*(i-1+j-1);//把该处的花费累加到仓库在(1,1)处的总花费上 36 ci[i][j]=ci[i-1][j]+ci[i][j-1]-ci[i-1][j-1]+x;//二维前缀和求出(1,1)到(i,j)的运输次数和 37 } 38 } 39 int ans=INF; 40 for(int i=1;i<=n;i++) 41 { 42 int t=sum; 43 for(int j=1;j<=m;j++)//根据该行首(i,1)的花费，遍历这一行每一列的花费 44 { 45 ans=min(ans,t); 46 t+=cal(1,1,n,j)-cal(1,j+1,n,m); 47 } 48 sum+=cal(1,1,i,m)-cal(i+1,1,n,m);//sum每次更新相当于求出了仓库在(1,1),(2,1)...(n,1)的花费 49 } 50 printf("%d ",ans); 51 } 52 53 return 0; 54 }
最后给出我看到的有意思的：
该方法来自参考于牛客用户Randolph、的博客
数学方法（O(NM)）
如果数据范围较大，方法一恐怕是过不了的。做过的同学可能会想到《算法竞赛进阶指南》0x05中的货仓选址，这一题是给出每个地点的坐标，每个地方只需去一次，求将货仓建在哪个坐标上到各点距离和最小，答案中货仓的坐标就是所有坐标中的中位数(所有数与中位数的绝对差之和最小。具体证明请看其题解，我也写了一篇哦qwq!，这里就不赘述了)
那么，我们可以用货仓选址中的中位数来解决这题吗？货仓选址与这一题很相似，但也有不同，有什么不同呢？
- 每个地方可能去多次：
我们想到，其实没必要按照题目中的一个地方去多次，可以改成多个地方，每个地方只去一次，这样就可做了 - 二维坐标：
想想能不能由一维的情况拓展到二维呢？其实也是可以的，我们先把每一行都看做一个整体，变成一维，再用中位数的方法找到最优行(即仓库选在这一行到其他行之间的距离和最小，其实就是选在这一行的仓库到其他行中地点的竖直距离和最小)；然后再把每一列都看做一个整体做一遍，得到最优列(即仓库选在这一列到其他列之间的距离和最小，也就是选在这一列的仓库到其他列中地点的水平距离和最小)，那么最终仓库在哪最优呢？当然是最优行与最优列的交点洛！
当然数学方法可能不太好理解，可以看看上面的方法二
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 using namespace std; 5 int s[110][2],x[110],y[110],ans[2],sum; 6 inline void get_pos(int num,int lim) {//求中位数到底位于哪一行或那一列，当然你不用二分直接扫一遍s数组判断也可以 7 int l=1,r=lim; 8 while(l<=r) { 9 int mid=(l+r)/2; 10 if (s[mid][num]<sum/2) l=mid+1;//sum/2，中位数，也就是最优的位置 11 else r=mid-1,ans[num]=mid;//返回最优行最优列的位置 12 } 13 } 14 int main() { 15 int T,n,m,_ans; 16 scanf("%d",&T); 17 while(T--) { 18 scanf("%d%d",&m,&n),sum=_ans=0; 19 memset(x,0,sizeof x); 20 memset(y,0,sizeof y); 21 for (int i=1,a; i<=n; i++) 22 for (int j=1; j<=m; j++) { 23 scanf("%d",&a),sum+=a;//sum统计一共有多少个地方，实际上把一个地方去a次，改成了a个地方，每个地方只去一次 24 x[i]+=a,y[j]+=a;//x,y分别统计每行、每列的数字和，即把每行、每列看为一个整体 25 } 26 for (int i=1; i<=n; i++) s[i][0]=s[i-1][0]+x[i]; 27 for (int i=1; i<=m; i++) s[i][1]=s[i-1][1]+y[i];//前缀和 28 get_pos(0,n),get_pos(1,m);//找最优行与最优列 29 for (int i=1; i<=n; i++) _ans+=abs(ans[0]-i)*x[i];//计算所有竖直距离 30 for (int i=1; i<=m; i++) _ans+=abs(ans[1]-i)*y[i];//计算所有水平距离 31 //当然这个计算答案用二维的(abs(x - i) + abs(y - j))也可以 32 printf("%d ",_ans); 33 } 34 }
-