1392C.md (2383B)
1 Source: https://codeforces.com/problemset/problem/1392/C 2 3 C. Omkar and Waterslide 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 Omkar is building a waterslide in his water park, and he needs your help to ensure that he does it as efficiently as possible. 22 23 Omkar currently has $n$ supports arranged in a line, the $i$-th of which has height $a_i$. Omkar wants to build his waterslide from the right to the left, so his supports must be nondecreasing in height in order to support the waterslide. In $1$ operation, Omkar can do the following: take any contiguous subsegment of supports which is nondecreasing by heights and add $1$ to each of their heights. 24 25 Help Omkar find the minimum number of operations he needs to perform to make his supports able to support his waterslide! 26 27 An array $b$ is a subsegment of an array $c$ if $b$ can be obtained from $c$ by deletion of several (possibly zero or all) elements from the beginning and several (possibly zero or all) elements from the end. 28 29 An array $b_1, b_2, \dots, b_n$ is called nondecreasing if $b_i\le b_{i+1}$ for every $i$ from $1$ to $n-1$. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 100$). Description of the test cases follows. 34 35 The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of supports Omkar has. 36 37 The second line of each test case contains $n$ integers $a_{1},a_{2},...,a_{n}$ $(0 \leq a_{i} \leq 10^9)$ — the heights of the supports. 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, output a single integer — the minimum number of operations Omkar needs to perform to make his supports able to support his waterslide. 44 45 Example 46 47 Input 48 49 ``` 50 3 51 4 52 5 3 2 5 53 5 54 1 2 3 5 3 55 3 56 1 1 1 57 ``` 58 59 Output 60 61 ``` 62 3 63 2 64 0 65 ``` 66 67 Note 68 69 The subarray with which Omkar performs the operation is bolded. 70 71 In the first test case: 72 73 * First operation: 74 75 $[5, 3, \textbf{2}, 5] \to [5, 3, \textbf{3}, 5]$ 76 * Second operation: 77 78 $[5, \textbf{3}, \textbf{3}, 5] \to [5, \textbf{4}, \textbf{4}, 5]$ 79 * Third operation: 80 81 $[5, \textbf{4}, \textbf{4}, 5] \to [5, \textbf{5}, \textbf{5}, 5]$ 82 83 In the third test case, the array is already nondecreasing, so Omkar does $0$ operations.