题目翻译
一个 $n\times m$ 的网格,每个格子里有 $1$ 个数,问对于所有相同的数,曼哈顿距离总和是多少?
曼哈顿距离:$a_{i_1,j_1}$ 与 $a_{i_2,j_2}$ 距离为 $\left|i_1-i_2\right|+\left|j_1-j_2\right|$。
题目思路
暴力搜一遍,肯定挂掉,$n\times m$ 有 $100000$。
所以,我们对每种数进行分类,每一类再分成 $x$ 轴的总距离求和加上 $y$ 轴的总距离求和。
这是蒟蒻我能想到的最优解了。
分析思路
那么总距离求和该怎么做呢,例如上文的 $x$ 轴的总距离求和。
我们考虑把它们排序,放在一根数轴上。
我们以端点为 $i_2$ 和 $i_3$ 的线段做例子:
本身长度 $2$。
往右边走,有 $i_3,i_4,i_5$,产生 $3$ 次贡献。
左边每个点都可以与上面 $3$ 个点产生连接,左边有 $2$ 个点,$i_1$ 和 $i_2$。
注意,线段的两个端点也算进去。
那么这个线段产生左边端点个数 $\times$ 线段长度 $\times$ 右边端点个数这么多贡献。
同理,每个线段也产生上述贡献。
AC 代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
int x,y;//记录x轴和y轴
};
vector<node>a[100020];//对数字分类
ll s(vector<int>a)//求和
{
ll sum=0;
for(int i=1;i<a.size();i++)
{
sum+=i*(a[i]-a[i-1])*(a.size()-i);
}
return sum;
}
void solve()
{
int n,m,maxx=INT_MIN;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int z;
cin>>z;
node zz;
zz.x=i;
zz.y=j;
a[z].push_back(zz);//插入这个点信息
maxx=max(z,maxx);//找出最大值
}
}
ll sum=0;
for(int i=1;i<=maxx;i++)
{
vector<int>xx;//记录x轴
vector<int>yy;//记录y轴
for(auto j:a[i])//插入点的信息
{
xx.push_back(j.x);
yy.push_back(j.y);
}
//排序
sort(xx.begin(),xx.end());
sort(yy.begin(),yy.end());
ll sx=s(xx);
ll sy=s(yy);
sum+=sx+sy;//求和
}
cout<<sum<<endl;
}
int main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}