Блог пользователя jaswanthi

Автор jaswanthi, история, 9 лет назад, По-английски

While the Codechef MNMX problem is easy, I am trying to solve it by changing the constraint to following.

Select a pair of adjacent integers and remove the **smaller** one and keeping the larger one. And the cost is larger one( while the original problem removes the **larger** one) 

In original problem, We are removing the larger one and keeping the smaller one, so We can start with smaller one and do it n-1 times. So the sum_of_cost = (n-1) * min_element

How to solve it if we change the constraint to remove smaller one and keep larger one, and the cost is the larger one ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

While removing smaller one and keeping larger one if the cost incurred is by larger one, then it will be same as (n-1)*largestcost

Otherwise if the cost incurred is by the smallest one only then answer would be (sum of total cost — cost of largest integer in array)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The best way to remove an element ai is to pair it with an element just >= ai.Thus the answer is always total — minimum element.