codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.