CF1648A-Weird Sum

2022-04-28 题解

题目大意：给出一个的网格，网格上的点都有一个颜色。问颜色相同的所有点两两之间的曼哈顿距离之和。

首先，曼哈顿距离横着竖着可以分开考虑，这题相当于求出颜色相同的点两两之间横着的距离跟竖着的距离后相加。求法大同小异，这里只说求横着的距离。

假设有x个颜色相同的点，横坐标分别为 $a_1,a_2,a_3,...,a_x$ 。要求的值就是

\sum_{i=1}^{x-1}\sum_{j=i+1}^{x}|a_j-a_i|

如果 $a[]$ 是有序的，保证 $a_j \geq a_i$ ，那么上式的绝对值符号可以去掉，化为

\sum_{i=1}^{x-1}\sum_{j=i+1}^{x}(a_j-a_i) \\ = \sum_{i=1}^{x}(i-1-(x-i))a_i \\ = \sum_{i=1}^{x}(2i-1-x)a_i

这题数据存储比较恶心，用了一些STL。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, i, j, t;
    map<int, multiset<long long>> mpi, mpj;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            scanf("%d", &t);
            mpi[t].insert(i);
            mpj[t].insert(j);
        }
    }
    long long res = 0;
    for (auto mit = mpi.begin(); mit != mpi.end(); mit++)
    {
        i = 1;
        int x = mit->second.size();
        for (auto it = mit->second.begin(); it != mit->second.end(); it++, i++)
            res += *it * (2 * i - 1 - x);
    }
    for (auto mit = mpj.begin(); mit != mpj.end(); mit++)
    {
        i = 1;
        int x = mit->second.size();
        for (auto it = mit->second.begin(); it != mit->second.end(); it++, i++)
            res += *it * (2 * i - 1 - x);
    }
    printf("%lld", res);
    return 0;
}