codeforces-scrape

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

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.