题意解析
本题要求我们求
i=1∑N−1j=i+1∑N∣Ai−Aj∣
带着这个绝对值是不好做,我们考虑把绝对值符号去掉。
上面这个式子本意就是求数组中元素两两之间的差的绝对值,数组的顺序是不影响答案的,所以我们可以把整个数组排序得到数组 A′:
A1′,A2′,A3′,⋯,AN′(A1′≤A2′≤A3′≤⋯≤AN′)。
那么,我们可以将上式转化为:
i=1∑N−1j=i+1∑NAj′−Ai′
这样就可以把这个绝对值符号去掉,从而我们可以继续转化这个式子:
((A2′−A1′)+(A3′−A1′)+⋯+(AN′−A1′))+((A3′−A2′)+(A4′−A2′)+⋯+(AN′−A2′))+⋮((AN−1′−AN−2′)+(AN′−AN−2)′)+((AN′−AN−1′))
化简得到:
(A2′+A3′+⋯+AN′−A1′×(N−1))+(A3′+A4′+⋯+AN′−A2′×(N−2))+(AN−1′+AN′−AN−2′×2)+(AN′−AN−1′)
从上面这个结果我们可以发现,这个式子最终的答案就是算每个 Ai 在答案中产生的贡献,有加有减。
每个 Ai′ 会减掉 N−i 次,会加上 i−1 次,那么我们就可以得到最终的式子:
i=1∑N−1j=i+1∑N∣Ai−Aj∣=i=1∑N−1j=i+1∑NAj′−Ai′=i=1∑N(i×2−N+1)×Ai′
上面这个式子,我们只需要将排序后的 A′ 进行一次遍历计算即可。
AC 代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; cin >> _;
while (_--) {
int n; cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
sort(begin(a), end(a));
i64 res = 0;
for (int i = 0; i < n; ++i)
res += (i * 2LL - n + 1) * a[i];
cout << res << '\n';
}
return 0;
}
复杂度分析
将数组 A 排序的时间复杂度为 O(NlogN),遍历 A′ 计算答案的时间复杂度为 O(N),总的时间复杂度为: O(NlogN)。
有帮助,赞一个