wish_me's blog

By wish_me, history, 2 years ago, In English,

We have N (where N > 2) stones of various heights laid out in a row. Task is to make a pyramid from given array of stones. In a pyramid, height of the stones start from 1, increase by 1, until it reaches some value x, then decreases by 1 until it reaches 1 again i.e. the stones should be 1, 2, 3, 4…x – 1, x, x – 1, x – 2 … 1. All other stones not part of the pyramid should have a height 0. We cannot move any of the stones from their current position, however, by paying a fee of 1, we can reduce the heights of the stones. We wish to minimize the cost of building a pyramid. Output the minimum cost to build this pyramid.

N<10^3 height<10^4

Examples:

Input : 1 2 3 4 2 1

Output : 4

The best pyramid that can be formed in this case is:

1 2 3 2 1 0

The cost is thus:

(4 — 2) + (2 — 1) + (1 — 0) = 4

Input : 1 5 2

Output : 4

We make a pyramid 1 2 1

Input : 1 2 1

Output : 0

We already have a pyramid, we do not need to do any

further construction.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it