LIT2021015_AYUSH's blog

Minimum Cost to sort an array either ascending or descending
By LIT2021015_AYUSH, history, 12 days ago, In English

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?

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by LIT2021015_AYUSH (previous revision, new revision, compare).

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by LIT2021015_AYUSH (previous revision, new revision, compare).

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

subtract the index i from each element a[i] then find the minimum cost to make the array equal

→ Reply
  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem: https://codeforces.com/problemset/problem/713/C

This is now a well-known DP technique called slope trick, see here or here.

→ Reply