codeforces-scrape

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

1987B.md (1863B)


      1 Source: https://codeforces.com/problemset/problem/1987/B
      2 
      3 B. K-Sort
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given an array of integers $a$ of length $n$.
     22 
     23 You can apply the following operation any number of times (maybe, zero):
     24 
     25 * First, choose an integer $k$ such that $1 \le k \le n$ and pay $k + 1$ coins.
     26 * Then, choose exactly $k$ indices such that $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$.
     27 * Then, for each $x$ from $1$ to $k$, increase $a_{i_x}$ by $1$.
     28 
     29 Find the minimum number of coins needed to make $a$ non-decreasing. That is, $a_1 \le a_2 \le \ldots \le a_n$.
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     34 
     35 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.
     36 
     37 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the minimum number of coins needed to make $a$ non-decreasing.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 3
     53 
     54 1 7 9
     55 
     56 5
     57 
     58 2 1 4 7 6
     59 
     60 4
     61 
     62 1 3 2 4
     63 
     64 1
     65 
     66 179
     67 
     68 9
     69 
     70 344 12 37 60 311 613 365 328 675
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 0
     77 3
     78 2
     79 0
     80 1821
     81 ```
     82 
     83 Note
     84 
     85 In the first test case, $a$ is already sorted, so you don't have to spend any coins.
     86 
     87 In the second test case, the optimal sequence of operations is:
     88 
     89 * Choose $k = 2$ and the indices $2$ and $5$: $[ 2, \color{red}{1}, 4, 7, \color{red}{6} ] \rightarrow [2, 2, 4, 7, 7]$. This costs $3$ coins.
     90 
     91 It can be proven that it is not possible to make $a$ non-decreasing by spending less than $3$ coins.