CF1648A

沉石鱼惊旋 · 2022-03-10 22:10:41 · 题解

题目翻译

一个 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;
}