how to make the sequence a non-decreasing sequence with the minimum number of steps?_问答_开发者

Here is the problem states that

given a sequence of N integer numbers. At each step it is allowed to increase the value of any number by 1 or to decrease it by 1. The goal of the game is to make the sequence non-decreasing with the minimum number of ste开发者_如何学运维ps

For example, Given

3 2 -1 2 11

one can make this sequence a non-decreasing sequence in a 4 steps (Decrease 3 by 1 and increase -1 by 3).

 (-1) (0) (+3) (0) (0)

The sequence will become

2 2 2 2 11

How can I solve this ?

I have provided working code in C#. It can easily be ported to language of your choice. The time complexity is around n2. It can be optimized in the method GenerateSequenceForEveryIndex() if count is more than minimumValue.

using System;
using System.Collections.Generic;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            Sequence seq = new Sequence();
            seq.GenerateSequenceForEveryIndex();
            Console.ReadLine();
        }

    }

    class Sequence
    {
        int count;
        public Sequence()
        {
            // Get Number of inputs
            Console.WriteLine("Number of values? ");
            this.count = int.Parse(Console.ReadLine());
            Console.WriteLine("Enter input values followed by RETURN/ENTER");
            GetInputSequence();
        }

        List<int> inputSequence = new List<int>();
        private void GetInputSequence()
        {
            for (int index = 0; index < count; index++)
                inputSequence.Add(int.Parse(Console.ReadLine()));
        }

        internal void GenerateSequenceForEveryIndex()
        {
            int minimumValue = 0;
            for (int index = 0; index < count; index++)
            { 
                // Get output sequence for every index
                // You can make a decision to get the minimum of the moves
                int newValue = GenerateSequenceForCurrentIndex(index);
                if (minimumValue == 0 || minimumValue > newValue) minimumValue = newValue;
                Console.WriteLine("Number of moves: " + newValue);
                Console.WriteLine();
            }
            Console.WriteLine("Minimum number of moves: " + minimumValue);
        }

        private int GenerateSequenceForCurrentIndex(int index)
        {
            int numberOfMoves = 0;
            int[] newOutputSequence = new int[count];
            int[] differenceSequence = new int[count];
            this.inputSequence.CopyTo(newOutputSequence);
            for (int ind = 0; ind < count; ind++)
            {
                if (ind == index) continue;
                differenceSequence[ind] = (ind == 0 ? newOutputSequence[index] : newOutputSequence[ind - 1])
                    - newOutputSequence[ind];

                // If sorted as non-decreasing, continue
                if (ind > index && differenceSequence[ind] < 0) continue;

                numberOfMoves += Math.Abs(differenceSequence[ind]);
                newOutputSequence[ind] += differenceSequence[ind];

            }
            DisplaySequence(differenceSequence, "Diff Sequence: ");
            DisplaySequence(newOutputSequence, "New Sequence: ");
            return numberOfMoves;
        }

        private static void DisplaySequence(int[] newOutputSequence, string heading)
        {
            Console.Write(heading);
            for (int i = 0; i < newOutputSequence.Length; i++)
                Console.Write(newOutputSequence[i] + " ");
            Console.WriteLine();
        }
    }
}

Explanation of algorithm Each of the element value can act as a pivot value, meaning values on the left of it shall be equal to its own value and values on the right to be greater than or equal to its own value. Having said that there can be a maximum of 'n' unique non-descending sequences. Now the algorigthm takes each of the value (see method GenerateSequenceForEveryIndex) and generates new non-descending sequence.

Inside GenerateSequenceForCurrentIndex(), values on the left of index are made sure to be equal to array[index]. We don't have to worry about less than as that will already be taken care by different sequences (when index < current index). Values on the right hand side are ensured to be greater than or equal to the current value. Any difference is considered as additional moves (absolute value)

Finally, DisplaySequence() is just displaying the values from the sequence.

Well the problem states that you should strive for the minimum number of changes. Lets say that the last number is -1000000. If you run through the sequence sequentially you will end up having to add 1000002 to the last element to get a non-decreasing sequence, but the solution would fail to meet the requirement of using the minimum number of steps. Therefor it might be a good idea to run through the sequence once, recording the differences between the elements. Hope you catch my drift. (im not as clear in writing as my thoughts appear to my-self :-)

#include <stdio.h>
#include <stdlib.h>

int get_destination( int numbers[], int size ) {
    int i,j;
    int destination = 0;
    int swap_done = 0;
    for ( i = 0; i < size - 1; i++) {
        for (j = 0; j < size - 1; j++) {
            if ( numbers[j] > numbers[j + 1]){
                destination = j + 1;
                swap_done = 1;
            }
        }
        if ( swap_done ) {
                break;
        }
    }
    return destination;
}
int main( int argc, char **argv ) {
    #define SIZE 5
    //int numbers[SIZE]= {3, 2, -1, 2, 11};
    //int numbers[SIZE]= {1,2,3,4,5};
    int numbers[SIZE]= {2, 1, 1, 1, 1};
    int answer = 0;
    int dest = get_destination( numbers, SIZE);
    if ( dest ) {
        for ( int i = 0; i < SIZE - 1; i++) {
            answer = answer + abs( abs(numbers[i]) - abs(numbers[dest]));
        }
    }
    printf ( "ANSWER = %d\n", answer );
    return 0;
}

If you look at bubble sort, in the first pass of outer loop, it put the element in the correct place, I am trying to use that concept. once you find out the first pass swapping position, use it for your reference and adjust all the elements in the sequence with respect to that element.

The solution can be found at - http://codeforces.com/blog/entry/364

It says -

Note, that there exists a non-decreasing sequence, which can be obtained from the given sequence using minimal number of moves and in which all elements are equal to some element from the initial sequence (i.e. which consists only from the numbers from the initial sequence).

PROOF -

Suppose there is no optimal sequence where each element is equal to some element from the initial sequence. Then there is an element i which is not equal to any of the elements of {ai}. If the elements with numbers i-1 and i+1 are not equal to element i, then we can move it closer to ai and the answer will decrease. So there is a block of equal elements and all of them are not equal to any of the elements of the initial sequence. Note, that we can increase all block by 1 or decrease it by 1 and one of this actions will not increase the answer, so we can move this block up or down until all its elements will be equal to some element from the initial sequence.

ALGORITHM -

Suppose {ai} is the initial sequence, {bi} is the same sequence, but in which all elements are distinct and they are sorted from smallest to greatest. Let f(i,j) be the minimal number of moves required to obtain the sequence in which the first i elements are non-decreasing and i-th element is at most bj. In that case the answer to the problem will be equals to f(n,k), where n is the length of {ai} and k is the length of {bi}. We will compute f(i,j) using the following recurrences:

f(1,1)=|a1-b1|
f(1,j)=min{|a1-bj|,f(1,j-1)},  j>1
f(i,1)=|ai-b1|+f(i-1,1),  i>1
f(i,j)=min{f(i,j-1),f(i-1,j)+|ai-bj|},  i>1, j>1

The complexity is O(N2). To avoid memory limit one should note that to compute f(i,) you only need to know f(i-1,) and the part of i-th row which is already computed.

You have to find a sequence which is

integral
non decreasing
as closest as possible to the original in L^1 norm.

It is a convex integer optimization problem under constraints which seems very difficult to solve optimally.

I got the following idea:

Build groups of non decreasing sequences (in your example {3} {2} {-1 2 11})
Merge two groups, this reduces the number of groups by one or two.
If there is only one group, a non decreasing solution is found. If not, go back to step 2.

Merging: There are always two possibilities of merging two groups, adjust the left group or adjust the right group. I will show this on examples, the idea should be clear.

Ajust the right group:

   {2} {-1 2 11} --> {2} {2 2 11}
   {2} {-1 0 1}  --> {2} {2 2 2}

Adjust the left group:

   {3}   {2} --> {2}   {2}
   {2 3} {1} --> {1 1} {1}

Because there are always two ways to go (adjust right / adjust left group) you can use the steps in a backtracking algorithm (which remembers the best solution found so far).

Demonstration:

{3} {2} {-1 2 11}
adjust left group --> {2 2} {-1 2 11}
adjust left group --> {-1 -1 -1 2 11}

Solutions:

{-1 -1 -1  2 11} (adjust left, adjust left)   --> score 7
{ 2  2  2  2 11} (adjust left, adjust right)  --> score 4 (best)
{-1 -1 -1  2 11} (adjust right, adjust left)  --> score 7
{ 3  3  3  3 11} (adjust right, adjust right) --> score 6