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

Tokitsukaze 有一张n个顶点的完全图G, 顶点编号是1到n,编号为i的顶点的值是$a_{i}$。

完全图指的是每对顶点之间都恰好有一条无向边的图。对于顶点u和顶点v之间的无向边,边权计算方式如下:

$$ w{u,v}=\begin{cases} 0 & \text{if } u=v \ |a{u} + a{v}| + |a{u} - a_{v}| & \text{if } 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≤T≤2⋅10^5),表示T组测试数据。

对于每组测试数据:

第一行包含一个整数n (1≤n≤2⋅10^5),表示完全图G的顶点数量。

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

保证$\sum{i=1}^{n}\sum{j=1}^{n}$ 不超过2⋅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
840
160
148
164

说明: 第二组测试数据,图G如下:

显然,dist(1,2)=w${1,2}$=20, dist(1,3)=w${1,3}$=200, dist(2,3)=w$_{2,3}$=200。

所以$\sum{i=1}^{n} \sum{j=1}^{n} dist(i,j)=840$

题目分析

对于 $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 * max(a{i}, a_{j})$。

代码实现

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

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

0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status