Preparing NOJ

修建道路

1000ms 524288K

Description:

比特镇有 $$$n$$$ 个村庄,编号依次为 $$$1$$$ 到 $$$n$$$。现在需要修建 $$$n-1$$$ 条双向道路将这些村庄连通起来,每条道路的端点只能是这 $$$n$$$ 个村庄之一。准确地说,如果要修建一条直接连接村庄 $$$i$$$ 与村庄 $$$j$$$ 的双向道路 ($$$1\leq i\leq j\leq n$$$),那么需要支付 $$$\max_{i\leq k\leq j}\{a_k\}$$$ 的费用。

请写一个程序,找到一个总费用最小的修路方案,使得任意两个村庄都能通过这些道路直接或间接到达。

Input:

第一行包含一个正整数 $$$n$$$ ($$$1\leq n\leq 200\,000$$$),表示村庄的数量。

第二行包含 $$$n$$$ 个正整数 $$$a_1,a_2,\dots,a_n$$$ ($$$1\leq a_i\leq 10^9$$$)。

Output:

输出一行一个整数,即所需的最小总费用。

Sample Input:

4
2 8 5 4

Sample Output:

21

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021年中国大学生程序设计竞赛女生专场

Code GYM103389D

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 11/01/2021 22:24:22

Related

Nothing Yet