2154B.md (2293B)
1 Source: https://codeforces.com/problemset/problem/2154/B 2 3 B. Make it Zigzag 4 5 time limit per test 6 7 1.5 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 An arbitrary array of integers $b$ of length $m$ is considered awesome if for all $i$ ($1 \le i \lt m$): 22 23 * if $i$ is odd then $b_i \lt b_{i + 1}$ holds. 24 * if $i$ is even then $b_i \gt b_{i + 1}$ holds. 25 26 In other words, the following inequality is true: $b_1 \lt b_2 \gt b_3 \lt b_4 \ldots$ 27 28 You are given an array of positive integers $a$ of length $n$. You may do either of the following operations any number of times, in any order: 29 30 * operation $1$: select an integer $i$ ($1 \le i \le n$) and do: $a_i := \max(a_1,\ldots,a_i)$, that is, replace $a_i$ with the prefix max up to $i$. 31 * operation $2$: select an integer $i$ ($1 \le i \le n$) and then decrease $a_i$ by $1$. 32 33 Determine the minimum number of times you need to do operation $2$ to make $a$ awesome. Note that you do not need to minimise the number of times you perform operation $1$. 34 35 Input 36 37 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. 38 39 The first line of each test case contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the array $a$. 40 41 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$). 42 43 The sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each testcase, output the minimum cost to make $a$ awesome. 48 49 Example 50 51 Input 52 53 ``` 54 7 55 56 5 57 58 1 4 2 5 3 59 60 4 61 62 3 3 2 1 63 64 5 65 66 6 6 6 6 6 67 68 7 69 70 1 2 3 4 5 6 7 71 72 3 73 74 3 2 1 75 76 2 77 78 1 2 79 80 9 81 82 65 85 19 53 21 79 92 29 96 83 ``` 84 85 Output 86 87 ``` 88 0 89 90 1 91 92 3 93 94 6 95 96 1 97 98 0 99 100 13 101 ``` 102 103 Note 104 105 In the first test case, the array is already awesome so no operations need to be done. 106 107 In the second test case, $a$ can be made awesome as follows: 108 109 * use operation $2$ and decrease $a_1$ by $1$. $[\color{red}3, 3, 2, 1] \rightarrow [\color{red}2, 3, 2, 1]$. 110 * use operation $1$ and change $a_4$ to $\max(2, 3, 2, 1) = 3$. $[2, 3, 2, \color{red}1] \rightarrow [2, 3, 2, \color{red}3]$. 111 112 $[2, 3, 2, 3]$ is awesome as $2 \lt 3 \gt 2 \lt 3$. It can be proven that this is the minimum number of times operation $2$ needs to be performed.