2111C.md (2024B)
1 Source: https://codeforces.com/problemset/problem/2111/C 2 3 C. Equal Values 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a_1, a_2, \dots, a_n$, consisting of $n$ integers. 22 23 In one operation, you are allowed to perform one of the following actions: 24 25 * Choose a position $i$ ($1 \lt i \le n$) and make all elements to the left of $i$ equal to $a_i$. That is, assign the value $a_i$ to all $a_j$ ($1 \le j \lt i$). The cost of such an operation is $(i - 1) \cdot a_i$. 26 * Choose a position $i$ ($1 \le i \lt n$) and make all elements to the right of $i$ equal to $a_i$. That is, assign the value $a_i$ to all $a_j$ ($i \lt j \le n$). The cost of such an operation is $(n - i) \cdot a_i$. 27 28 Note that the elements affected by an operation may already be equal to $a_i$, but that doesn't change the cost. 29 30 You are allowed to perform any number of operations (including zero). What is the minimum total cost to make all elements of the array equal? 31 32 Input 33 34 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 35 36 The first line of each test case contains a single integer $n$ ($2 \le n \le 5 \cdot 10^5$). 37 38 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$). 39 40 The sum of $n$ over all test cases does not exceed $5 \cdot 10^5$. 41 42 Output 43 44 For each test case, print a single integer — the minimum total cost of operations to make all elements of the array equal. 45 46 Example 47 48 Input 49 50 ``` 51 3 52 53 4 54 55 2 4 1 3 56 57 3 58 59 1 1 1 60 61 10 62 63 7 5 5 5 10 9 9 4 6 10 64 ``` 65 66 Output 67 68 ``` 69 3 70 0 71 35 72 ``` 73 74 Note 75 76 In the first test case, you can perform the operation twice: 77 78 * choose $i = 3$ and make all elements to the left of it equal to it, the cost will be $2 \cdot 1 = 2$; 79 * choose $i = 3$ and make all elements to the right of it equal to it, the cost will be $1 \cdot 1 = 1$. 80 81 The total cost is $2 + 1 = 3$. 82 83 In the second test case, all elements are already equal, so no operations need to be performed.