链接
https://ac.nowcoder.com/acm/contest/4462/G
题意
给出一个 $m \times n$ 的矩阵，每个点都有一个访问次数，找出以某点为起点到其他点的距离 $*$ 访问次数之和最小
思路
前缀和
若仓库在点 $(x,y)$ 处，现在将仓库移动到点 $(x+1,y)$ ，那么对于左上角为 $(1,1)$，右下角为 $(x,m)$ 的矩阵，所有点到达仓库的距离都 $+1$，对于左上角为 $(x+1,1)$，右下角为 $(n,m)$ 的矩阵，所有点到达仓库的距离都 $-1$。若仓库在点 $(x,y)$ 处，现在将仓库移动到点 $(x,y+1)$ 同理计算即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
int s[N][N];
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];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;
while(T--) {
cin>>m>>n;
int now=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
int x;
cin>>x;
now+=x*(i-1+j-1);
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
}
}
int res=0x3f3f3f3f;
for(int i=1;i<=n;i++) {
for(int j=1,t=now;j<=m;j++) {
res=min(res,t);
t+=calc(1,1,n,j)-calc(1,j+1,n,m);
}
now+=calc(1,1,i,m)-calc(i+1,1,n,m);
}
cout<<res<<endl;
}
return 0;
}
|