题意:
计算\(\sum\limits_{i = 1}^{N}\sum\limits_{j = 1}^{N}min(\vert p_i - p_j\vert, \vert q_i - q_j\vert)\)
思路:
可以转换为\(\sum\limits_{i = 1}^{N}\sum\limits_{j = 1}^{N}(|p_i - p_j| + |q_i - q_j|) - \sum\limits_{i=1 =1}^{N}\sum\limits_{j = 1}^{N}max(|p_i - p_j|, |q_i - q_j|)\)
首先， 求曼哈顿距离，令 tp = q， tq = q 先对tp, tq进行排序, 然后求tp, tq的前缀和，在对每一个p, q进行lower_bound找到位置，直接相减处理
其次，先介绍下切比雪夫距离，\(max(|x1 - x2|, |y1 - y2|)\), 和上述的式子一比较，发现一模一样，\(p_i = x1, p_j = x2, q_i = y1, q_j = y2\), 切比雪夫距离可以转换成曼哈顿距离，\(max(|x1 - x2|, |y1 - y2|)\) = \(|(x1 + y1) / 2 - (x2 + y2) / 2| + |(x1 - y1) / 2 + (x2 - y2) / 2|\), 利用这个转换成曼哈顿就可以直接计算求值了
总结:
曼哈顿可以用前缀和和sort来处理，切比雪夫可以转成曼哈顿
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);
#define endl '\n'
using namespace std;
typedef long long ll;
const ll MAXN = 1e6 + 10;
ll n;
ll p[MAXN], q[MAXN], tp[MAXN], tq[MAXN], sump[MAXN], sumq[MAXN], pqi[MAXN], pqj[MAXN], tpqi[MAXN], tpqj[MAXN], sumpqi[MAXN], sumpqj[MAXN];
int main()
{
IOS; cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> p[i], tp[i] = p[i];
for (int i = 1; i <= n; ++i)
cin >> q[i], tq[i] = q[i];
sort(tp + 1, tp + 1 + n);
sort(tq + 1, tq + 1 + n);
for (int i = 1; i <= n; ++i)
sump[i] = sump[i - 1] + tp[i], sumq[i] = sumq[i - 1] + tq[i];
ll sum = 0; //总的曼哈顿距离
for (int i = 1; i <= n; ++i)
{
int posp = lower_bound(tp + 1, tp + 1 + n, p[i]) - (tp);
int posq = lower_bound(tq + 1, tq + 1 + n, q[i]) - (tq);
//cout << "posp: " << posp << endl;
sum += abs(sump[posp] - (posp) * p[i]) + abs(sump[n] - sump[posp] - (n - posp) * p[i]);
sum += abs(sumq[posq] - (posq) * q[i]) + abs(sumq[n] - sumq[posq] - (n - posq) * q[i]);
}
//cout << "sum: " << sum << endl;
for (int i = 1; i <= n; ++i)
{
pqi[i] = (p[i] + q[i]);
tpqi[i] = pqi[i];
pqj[i] = (p[i] - q[i]);
tpqj[i] = pqj[i];
}
sort(tpqi + 1, tpqi + 1 + n);
sort(tpqj + 1, tpqj + 1 + n);
for (int i = 1; i <= n; ++i)
sumpqi[i] = sumpqi[i - 1] + tpqi[i], sumpqj[i] = sumpqj[i - 1] + tpqj[i];
ll mxsum = 0;
for (int i = 1; i <= n; ++i)
{
int posp = lower_bound(tpqi + 1, tpqi + 1 + n, pqi[i]) - tpqi;
int posq = lower_bound(tpqj + 1, tpqj + 1 + n, pqj[i]) - tpqj;
mxsum += abs(sumpqi[posp] - (posp) * pqi[i]) + abs(sumpqi[n] - sumpqi[posp] - (n - posp) * pqi[i]);
mxsum += abs(sumpqj[posq] - (posq) * pqj[i]) + abs(sumpqj[n] - sumpqj[posq] - (n - posq) * pqj[i]);
}
cout << sum - mxsum / 2 << endl;
return 0;
}