I_love_Jiang's blog

Please help me on this problem !
By I_love_Jiang, history, 8 years ago, In English

Link of the problem :http://www.spoj.com/problems/TOINCSEQ/

In short: You are given a sequence of non-negative integers a1, a2, …, an. You are allowed to perform some operators on the sequence. Each operator consists of 2 steps: choosing an arbitrary value, then increasing (or decreasing) all elements of the selected value in the current sequence by 1.

For example, the sequence 1 9 9 2 2 will become 1 9 9 3 3 if you decide to increase all elements of value 2.

What is the minimum number of operators does it take to make the given sequence a non-decreasing sequence?

Input

The first line consits of an integer N, the number of elements in the sequence. The second line consists of N elements of the sequence. Output

The mininum number of operators needed to make the sequence non-decreasing. Example

Input: 5

1 9 9 2 2

Output: 7 Constraints

1 ≤ N ≤ 10^5. Each element of the sequence is a non-negative integer not exceeding 10^9. ***************************************************************************

I think we can uses DP but I had no idea then.

Help me please !!!

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

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Remove duplicates from array. Question then becomes this
DP is O(n2). Idea for O(nlogn) is here

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

    Thank for your idea but it may have a few differences when we can increase all elements of the same value instead of one by one :)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      REMOVE DUPLICATES IN BEGINNING. Then the problem is same.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    what about this test case?
    5
    5 4 3 2 1
    ans = 4

    → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My solution: link
when there exist a value strictly less than the one before it add a segment [ ai , ai - 1 ]
answer is the union of those segments

→ Reply