题目大意

在 \(n\times n\) 的矩形中找出一个点，使得这个点到其他标记点曼哈顿距离加上所有标记点的权值之和最小。

解题思路

做法一:前缀和

比较显然的性质：任何一个特殊点到同一行的点的曼哈顿距离中经过的列数是一样的。

同理，所有的特殊点到同一列的点的曼哈顿距离中经过的行数是一样的。

那么我们设 \(h_i\) 表示所有特殊点到这一行的点曼哈顿距离经过的列数，\(l_i\) 表示所有特殊点到这一列的点曼哈顿距离经过的行数。

很容易发现：

\[h_i = h_{i − 1} + 在 第 i − 1 行 上 面 的 特 殊 点 数 量 − 在 第 i 行 下 面 的 特 殊 点 数 量 \]

特殊点数量可通过前缀和得出：

\[hs_i=hs_{i−1}+hnum_{i} \]

答案即为最小的 \(h_i\) 和最小的 \(l_i\) 交叉的那个点。

做法二：二维中位数

曼哈顿距离的横坐标和纵坐标距离是分开的，所以我们可以对横坐标和纵坐标分开看，分别取两个的中位数作为答案的坐标。

因为我们求的是所有特殊点的平均坐标值。

AC CODE

做法一

#include <bits/stdc++.h>
#define int long long
#define _ 100000 + 7
using namespace std;

int n, m, z;

int h[_], l[_], hnum[_], lnum[_], hs[_], ls[_];

int minn, sum, ansx, ansy;

signed main()
{
    scanf("%lld%lld%lld", &n, &m, &z);
    for (int i = 1; i <= m; i++)
    {
        int x, y, q;
        scanf("%lld%lld%lld", &x, &y, &q);
        hnum[x]++;
        lnum[y]++;
        sum += q;
    }
    for (int i = 1; i <= n; i++)
        hs[i] = hs[i - 1] + hnum[i];
    for (int i = 1; i <= n; i++)
        ls[i] = ls[i - 1] + lnum[i];
    for (int i = 1; i <= n; i++)
        h[1] += (hnum[i] * abs(i - 1) * z);
    for (int i = 1; i <= n; i++)
        l[1] += (lnum[i] * abs(i - 1) * z);
    for (int i = 2; i <= n; i++)
        h[i] = h[i - 1] + hs[i - 1] * z - (m - hs[i - 1]) * z;
    for (int i = 2; i <= n; i++)
        l[i] = l[i - 1] + ls[i - 1] * z - (m - ls[i - 1]) * z;
    for (int i = 1; i <= n; ++i)
        cout << h[i] << " ";
    cout << endl;
    minn = LLONG_MAX;
    for (int i = 1; i <= n; i++)
        if (h[i] < minn)
        {
            minn = h[i];
            ansx = i;
        }
    minn = LLONG_MAX;
    for (int i = 1; i <= n; i++)
        if (l[i] < minn)
        {
            minn = l[i];
            ansy = i;
        }
    printf("%lld\n%lld %lld\n", h[ansx] + l[ansy] + sum, ansx, ansy);
    return 0;
}

做法二

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int _ = 100001;

int n, m, z, sum, y[_], x[_], tp;

signed main()
{
    scanf("%lld%lld%lld", &n, &m, &z);
    for (int i = 1; i <= m; i++)
    {
        scanf("%lld%lld%lld", &x[i], &y[i], &tp);
        sum += tp;
    }
    int mid = ceil((double)m / 2);
    sort(x + 1, x + m + 1);
    sort(y + 1, y + m + 1);
    for (int i = 1; i <= m; i++)
        sum += abs(x[i] - x[mid]) + abs(y[i] - y[mid]);
    printf("%lld\n%lld %lld\n", sum, x[mid], y[mid]);
    return 0;
}