如何用最少的步骤使一个序列成为非递减序列？

Question

这里是问题陈述：

给定一个由N个整数组成的序列。每一步可以将任何数字的值增加1或减少1。游戏的目标是以最少的步骤使序列非递减。

例如，给定

3 2 -1 2 11

我们可以在4步内使此序列成为非递减序列（将3减1并将-1增加3）。

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

序列将变为：

2 2 2 2 11

我该如何解决这个问题？

- user467871

---

最少步数的意义是什么？ - Avinash

@Avinash，这不是最小步数，而是最少步数。例如，在3 2 -1 2 11的情况下，为了使其非递减需要进行4次更改，即(-1) (0) (+3) (0) (0)，分别对应每个整数。 - Sandeep G B

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]。我们不必担心小于号，因为不同的序列已经处理好了（当index <当前索引时）。右侧的值被确保大于或等于当前值。任何差异都被视为额外的移动（绝对值）

最后，DisplaySequence()只显示序列中的值。

- Sandeep G B

---

我已经提供了解释。如果它回答了你的问题，请将其标记为已回答。 - Sandeep G B

为什么它是最小的？在我看来，如果答案没有包含最优性证明，那么不应该接受任何答案。 - Alexandre C.

@Alexandre，在GenerateSequenceForEveryIndex()方法中，进行了检查以确保选择最小值。循环确保生成所有可能的序列。 - Sandeep G B

Answer 2

解决方案可以在此找到 - http://codeforces.com/blog/entry/364 它说 -

请注意，存在一个非递减序列，可以通过使用最少的步骤从给定序列中获得，并且其中所有元素都等于初始序列中的某个元素（即仅由初始序列中的数字组成）。

证明 -

假设没有每个元素都等于初始序列中的某个元素的最佳序列。然后有一个元素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行的部分。

- user1412066

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

如果你看一下冒泡排序，第一次外层循环就把元素放在正确的位置上了，我正试图使用这个概念。一旦你找到了第一次交换的位置，就用它作为参考，并根据那个元素调整序列中的所有元素。

- Avinash

---

以下是有关编程的内容，请将其翻译成中文。只返回翻译后的文本：请回答您的算法。对我来说，编码并不重要。无论如何，感谢您的支持。 - user467871

对于序列 {3, 2, -1, 11, 11}，你的算法给出了答案13。实际上应该是4。 - Christian Ammer

Answer 4

好的，问题陈述了你应该努力实现最小数量的更改。 假设最后一个数字是-1000000。 如果您按顺序运行序列，则最终必须将1000002添加到最后一个元素以获得非递减序列，但解决方案将无法满足使用最少步骤的要求。 因此，通过运行一次序列并记录元素之间的差异可能是个好主意。希望你能理解我的意思。（我写作不够清晰，但我自己的想法很清楚 :-)）

- jens lyn haahr

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

- Christian Ammer

Answer 6

你需要找到一个符合以下要求的序列:

1. 整数
2. 非递减
3. 在L^1范数下尽可能接近原始序列。

这是一个带有限制条件的凸整数优化问题，似乎很难找到最佳解。

- Alexandre C.