Plus 与 minus 的唯一区别是边权的计算方式。

Tokitsukaze 有一张 $n$ 个顶点的完全图 $G$, 顶点编号是 $1$ to $n$,编号为 $i$ 的顶点的值是 $a_i$。

完全图指的是每对顶点之间都恰好有一条无向边的图。对于顶点 $u$ 和顶点 $v$ 之间的无向边,边权计算方式如下: $$ w{u,v} = \begin{cases} 0, & u=v \ |a{u}+a{v}| - |a{u}-a_{v}|, & u \neq v \end{cases} $$

定义 $dist(i,j)$ 表示顶点 $i$ 为起点,顶点 $j$ 为终点的最短路。求 $\sum{i=1}^{n} \sum{j=1}^{n} dist(i,j)$

关于最短路的定义:

定义一条从 $s$ 到 $t$ 的路径为若干条首尾相接的边形成的序列且该序列的第一条边的起点为 $s$,最后一条边的终点为 $t$,特别的,当 $s=t$ 时该序列可以为空。

定义一条从 $s$ 到 $t$ 的路径长度为该路径中边权的总和。

定义 $s$ 到 $t$ 的最短路为 $s$ 到 $t$ 所有路径长度中的最小值。

输入格式

第一行包含一个整数 $T (1 \leq T \leq 2 \cdot 10^{5})$,表示 $T$ 组测试数据。

对于每组测试数据:

第一行包含一个整数 $n (1 \leq n \leq 2 \cdot 10^{5})$,表示完全图 $G$ 的顶点数量。

第二行包含 $n$ 个整数 $a{1}$, $a{2}$, …, $a{n}$ $(1 \leq a{i} \leq 2 \cdot 10^{5})$,表示完全图 $G$ 的每个顶点的值。

保证 $\sum _{n}$ 不超过 $2 \cdot 10^{5}$。

输出格式

对于每组测试数据,输出一个整数表示答案。

输入样例:

5
1
1
3
10 1 100
5
1 2 3 4 5
4
2 3 5 8
5
1 3 3 4 5

输出样例:

0
16
64
64
64

题目分析

对于 $a{u}$ -> $a{v}$ ($u \neq v$):

$$ W{u,v} = |a{u} + a{v}| + |a{u} - a_{v}| $$

  • $u > v$

$$ W{u,v} = a{u} + a{v} + a{u} - a{v} = 2 * a{u} $$

  • $u < v$

$$ W{u,v} = a{u} + a{v} - a{u} + a{v} = 2 * a{v} $$

我们可以知道:

$$ W{u,v} = 2 * max(a{u}, a_{v}) $$

由于 $a{i} \geq 1$,所以 $dist(i, j) = 2 * min(a{i}, a_{j})$。

由于是取 min, 我们可以考虑绕路的情况: $ a{i} -> a{j} = 2 min(a{i}, a{j}) $ $ a{i} -> min(a) - > a{j} = 4 min(a) $ 可以知道, 只要 2 min(a{i}, a{j}) > 4 min(a) , 那么绕路是最好的选择。

那么我们将 a 从小到大排序, 枚举每个 $ a_{i} $ 作为 max 。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;

int t;
void solve() {
    int n;
    cin >> n;
    vector <int> a(n);
    for(auto& ai : a) cin >> ai;
    sort(a.begin(), a.end());
    LL ans = 0;
    for(int i = 0; i < n; ++i) {
        if(2 * a[i] <= 4 * a[0]) ans += (n - i - 1) * 1ll * a[i] * 2;
        else ans += (n - i - 1) * 1ll * a[0] * 4;
    }
    cout << (ans << 1) << '\n';
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}
分类: MathSort

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status