Given an array of integers ,the cost to change an element is abs(newvalue — initialvalue) .Determine the minimum cost to sort the array either ascending or descending .
1<=n<=1e3 1<=arr[i]<=1e9
I couldnt find its solution after so much brainstorming can anyone help me out with its solution?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Auto comment: topic has been updated by LIT2021015_AYUSH (previous revision, new revision, compare).
Auto comment: topic has been updated by LIT2021015_AYUSH (previous revision, new revision, compare).
subtract the index i from each element a[i] then find the minimum cost to make the array equal
Well if we have 1,7,5,5 we can choose a[1] and change 7 to 5 with cost of 2 and this is the minimum cost to sort this array .
Can u explain ur approach on this example?
Problem: https://codeforces.com/problemset/problem/713/C
This is now a well-known DP technique called slope trick, see here or here.
Thanks for help .