codeforces-scrape

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

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.