[COCI 2021/2022 #4] Autići

Luogu

IDLGP8311

Time1000ms

Memory512MB

DifficultyP2

2021COCI（克罗地亚）

有 $n$ 个好朋友，每人有一辆遥控汽车和一个车库。第 $i$ 个人有若干个长度为 $d_i$ 的玩具道路部件，可以为汽车建造道路。两个朋友 $a$ 和 $b$ 可以建造一条长度为 $d_a+d_b$ 道路以连接他们的车库。我们认为，如果从任意一个车库出发能够到达任意的其他车库，我们称这种情况为“连通交通”。请求出，构成一个“连通交通”所需要的最小总道路长度是多少？ ## Input 第一行包含一个整数 $n$，表示朋友的人数。第二行包含 $n$ 个整数 $d_i$，表示第 $i$ 位朋友手中的道路部件的长度。 ## Output 仅一行，输出成一个“连通交通”所需要的最小总道路长度。 [samples] ## Note **【样例 1 解释】** 当只有一位朋友时，已经构成“连通交通”，不必修建道路。故答案为 $0$。 **【样例 3 解释】** 如果在第 $1$ 位和第 $2$ 位朋友、第 $2$ 位和第 $3$ 位朋友、第 $3$ 位和第 $4$ 位朋友之间修建道路可以形成“连通道路”，价格总和为 $(7+3)+(3+3)+(3+5)=24$。 **【数据规模与约定】** **本题采用子任务捆绑测试。** - Subtask 1（10 pts）：$d_1 = d_2 = \dots = d_n$。 - Subtask 2（20 pts）：$1 ≤ n ≤ 10^3$。 - Subtask 3（20 pts）：没有额外限制。对于 $100\%$ 的数据，$1\le n\le10^5,1\le d_i\le 10^9$。 **【提示与说明】** **本题分值按 COCI 原题设置，满分 $50$。** **题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T1 Autići。**

Samples

Input #1

1
10

Output #1

Input #2

3
5 5 5

Output #2

Input #3

4
7 3 3 5

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2021/2022 #4] Autići",
    "description": {
      "content": "有 $n$ 个好朋友，每人有一辆遥控汽车和一个车库。第 $i$ 个人有若干个长度为 $d_i$ 的玩具道路部件，可以为汽车建造道路。 两个朋友 $a$ 和 $b$ 可以建造一条长度为 $d_a+d_b$ 道路以连接他们的车库。 我们认为，如果从任意一个车库出发能够到达任意的其他车库，我们称这种情况为“连通交通”。 请求出，构成一个“连通交通”所需要的最小总道路长度是多少？",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8311"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个好朋友，每人有一辆遥控汽车和一个车库。第 $i$ 个人有若干个长度为 $d_i$ 的玩具道路部件，可以为汽车建造道路。\n\n两个朋友 $a$ 和 $b$ 可以建造一条长度为 $d_a+d_b$ 道路以连接他们的车库。\n\n我们认为，如果从任意一个车库出发能够到达任意的其他车库，我们称这种情况为“连通交通”。\n\n请求出，构成一个“连通交通”所需要的最小总道路长度是多少？\n\n## Input...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments