2165A.md (1927B)
1 Source: https://codeforces.com/problemset/problem/2165/A 2 3 A. Cyclic Merging 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given $n$ non-negative integers $a_1,a_2,\ldots,a_n$ arranged on a ring. For each $1\le i \lt n$, $a_i$ and $a_{i+1}$ are adjacent; $a_1$ and $a_n$ are adjacent. 22 23 You need to perform the following operation exactly $n-1$ times: 24 25 * Choose any pair of adjacent elements on the ring, let their values be $x$ and $y$, and merge them into a single element of value $\max(x,y)$ with cost $\max(x,y)$. 26 27 Note that this operation will decrease the size of the ring by $1$ and update the adjacent relationships accordingly. 28 29 Please calculate the minimum total cost to merge the ring into one element. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 34 35 The first line of each test case contains an integer $n$ ($2\le n\le 2\cdot 10^5$). 36 37 The following line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i \le 10^9$). 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 40 41 Output 42 43 For each test case, please print a single integer — the minimum total cost. 44 45 Example 46 47 Input 48 49 ``` 50 3 51 52 4 53 54 1 1 3 2 55 56 2 57 58 0 2 59 60 7 61 62 1 1 4 5 1 4 1 63 ``` 64 65 Output 66 67 ``` 68 6 69 70 2 71 72 19 73 ``` 74 75 Note 76 77 In the first test case, we can achieve a cost of $6$ on $[1,1,3,2]$ as follows: 78 79 * Merge indexes $1$ and $2$ with a cost of $1$, the ring becomes $[1,3,2]$. 80 * Merge indexes $1$ and $3$ with a cost of $2$, the ring becomes $[3,2]$. 81 * Merge indexes $1$ and $2$ with a cost of $3$, the ring becomes $[3]$. 82 83 The total cost is $1+2+3=6$. It can be proven that it is impossible to achieve a lower cost; thus, the answer is indeed $6$. 84 85 In the second test case, the only option is to merge the two elements, with a cost of $2$.