как сделать последовательность неубывающей последовательностью с минимальным количеством шагов?

Question

Вот проблема утверждает, что

дана последовательность из N целых чисел. На каждом шаге разрешается увеличивать значение любого числа на 1 или уменьшать его на 1. Цель игры - сделать последовательность неубывающей с минимальным количеством шагов

Например, учитывая

3 2 -1 2 11

можно сделать эту последовательность неубывающей последовательностью с шагом 4 (уменьшение 3 на 1 и увеличение -1 на 3).

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

Последовательность станет

2 2 2 2 11

Как я могу решить это?

Answer 1

Я предоставил рабочий код на C #.Его можно легко перенести на язык по вашему выбору.Сложность времени составляет около n2.Он может быть оптимизирован в методе GenerateSequenceForEveryIndex (), если число больше, чем минимальное значение.

---

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();
        }
    }
}

---

Объяснение алгоритма Каждое значение элемента может действовать каксводное значение, означающее, что значения слева от него должны быть равны его собственному значению, а значения справа должны быть больше или равны его собственному значению.Сказав, что может быть максимум «n» уникальных не убывающих последовательностей.Теперь алгоритм принимает каждое значение (см. Метод GenerateSequenceForEveryIndex) и генерирует новую не убывающую последовательность.

Внутри GenerateSequenceForCurrentIndex () значения слева от индекса обязательно равны массиву [index].Нам не нужно беспокоиться о чем-то меньшем, поскольку об этом уже позаботятся различные последовательности (когда индекс <текущий индекс).Значения справа должны быть больше или равны текущему значению.Любая разница считается дополнительным ходом (абсолютное значение) </p>

Наконец, DisplaySequence () просто отображает значения из последовательности.

Answer 2

Решение можно найти по адресу - http://codeforces.com/blog/entry/364

Это говорит -

Обратите внимание, что существует неубывающая последовательность, которая может быть получена из данной последовательности с использованием минимального числаходов и в котором все элементы равны некоторому элементу из начальной последовательности (т.е. который состоит только из чисел из начальной последовательности).

PROOF -

Предположим, что оптимальной последовательности не существуетгде каждый элемент равен некоторому элементу из начальной последовательности.Тогда есть элемент i, который не равен ни одному из элементов {ai}.Если элементы с номерами i-1 и i + 1 не равны элементу i, то мы можем переместить его ближе к ai, и ответ уменьшится.Таким образом, существует блок равных элементов, и все они не равны ни одному из элементов исходной последовательности.Обратите внимание, что мы можем увеличить весь блок на 1 или уменьшить его на 1, и одно из этих действий не увеличит ответ, поэтому мы можем перемещать этот блок вверх или вниз, пока все его элементы не будут равны какому-либо элементу из начальной последовательности.

АЛГОРИТМ -

Предположим, {ai} - это начальная последовательность, {bi} - та же самая последовательность, но в которой все элементы различны, и они отсортированы от наименьшего к наибольшему.Пусть f (i, j) - минимальное число ходов, необходимое для получения последовательности, в которой первые элементы i неубывающие, а i-й элемент не больше bj.В этом случае ответ на задачу будет равен f (n, k), где n - длина {ai}, а k - длина {bi}.Мы вычислим f (i, j), используя следующие повторения:

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

Сложность O (N2).Чтобы избежать ограничения памяти, следует помнить, что для вычисления f (i, ) вам нужно знать только f (i-1, ) и ту часть i-й строки, которая уже вычислена.

Answer 3

#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;
}

Если вы посмотрите на сортировку пузырьков, то в первом проходе внешнего цикла он поместит элемент в правильное место, я пытаюсь использовать эту концепцию.Как только вы узнаете позицию обмена первого прохода, используйте ее для справки и отрегулируйте все элементы в последовательности относительно этого элемента.

Answer 4

Ну, проблема в том, что вы должны стремиться к минимальному количеству изменений. Допустим, последний номер -1000000. Если вы выполните последовательность последовательно, вам придется добавить 1000002 к последнему элементу, чтобы получить неубывающую последовательность, но решение не будет соответствовать требованию использования минимального количества шагов. Для этого может быть хорошей идеей выполнить последовательность один раз, записав различия между элементами. Надеюсь, вы поймаете мой дрейф. (Я не так ясно пишу, как мои мысли кажутся мне: -)

Answer 5

У меня появилась следующая идея:

1. Создание групп неубывающих последовательностей (в вашем примере {3} {2} {-1 2 11})
2. Объединение двух групп, это уменьшает количество групп на одну или две.
3. Если существует только одна группа, найдено неубывающее решение. Если нет, вернитесь к шагу 2.

Объединение: Всегда есть две возможности объединения двух групп, настройте левая группа или настроить правую группу. Я покажу это на примерах, идея должна быть ясной.

Настройте правильную группу:

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

Настройте левую группу:

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

Потому что всегда есть два пути (отрегулировать вправо / отрегулировать левую группу) Вы можете использовать шаги в алгоритме возврата (который запоминает лучшее Решение найдено).

Демонстрация:

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

Решения:

{-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

Answer 6

Вы должны найти последовательность, которая

1. интеграл
2. неубывающий
3. как можно ближе к оригиналу в норме L ^ 1.

Это выпуклая целочисленная задача оптимизации при ограничениях, которая кажется очень сложной для оптимального решения.