有什么更好的方法来解决这个问题？该问题涉及IT技术。

Question

有什么更好的方法来解决这个问题？该问题涉及IT技术。

4

我正在尝试解决的问题是：给定一个有2行N列的表格，每个单元格都有一个整数。这个表格的分数定义如下：对于每一列，考虑该列中两个数字的和；得到的N个数字中的最大值就是该表格的分数。例如，对于表格7 1 6 2 1 2 3 4，其分数为max(7 + 1; 1 + 2; 6 + 3; 2 + 4) = 9。第一行固定且作为输入。考虑N种可能的方式来填充第二行：

1; 2; : : : ; N 2; 3; : : : ; N; 1 3; 4; : : : ; N; 1; 2 | N; 1; : : : ; ; N-1

例如，对于上面的例子，我们将考虑以下每种情况作为第二行：

1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3

你的任务是找出每种第二行选择的分数。例如，在上面的例子中，你将评估以下四个表格：

7 1 6 2 1 2 3 4

7 1 6 2 2 3 4 1

7 1 6 2 3 4 1 2

7 1 6 2 4 1 2 3

分别计算得分为9、10、10和11。

测试数据：N <= 200000 时间限制：2秒

明显的方法如下：

维护两个数组A，B。执行以下操作n次：

将A[i]的每个元素加到B[i]中，并保持一个变量max，该变量存储迄今为止的最大值。

打印max。

遍历数组B[i]，如果任何元素等于N，则将所有元素增加1；如果任何元素等于N，则将其设置为1。

此方法将需要O(n^2)的时间，外循环运行N次，而内部有两个循环，每个循环都运行N次。

为了减少时间，我们可以在第一行中找到最大元素M（进行线性扫描），并在A[i]+N<=M+1时删除A[i]和B[i]。因为它们永远不会是最大值。

虽然这种方法在平均情况下可能执行得更好，但最坏情况的时间仍将是O（N ^ 2）。

为了在恒定时间内找到最大值，我还考虑使用堆，堆的每个元素都有两个属性，它们的原始值和要添加的值。但仍需要线性时间来递增堆的所有元素的值以处理n个案例。
因此时间仍然保持为O（N ^ 2）

我无法找到比N ^ 2时间更快地解决此问题的方法，因为N的值可能非常大。
任何帮助都将不胜感激。

- 2147483647

由于主题行不太可能对未来访问者有所帮助（“过于局部化”），被点踩。 - Raymond Chen

2个回答

2

这里有一个O(n*logn)的解决方案：

假设你计算了第二行特定排列的所有列之和。

现在考虑当你将第二行向左旋转（例如，将其从1,2,...,N更改为2,3,...,N,1）时，列之和会发生什么变化：每个列之和都会增加1，除了一个列之和会减少N-1。

我们可以不修改所有列之和，而是将一个列之和减少N，然后取最大列之和加1来找到列之和的新最大值。因此，我们只需要更新一个列而不是所有列。

所以我们的算法是：

1.将第二行设置为1,2,...,N并计算每列之和。将所有这些总和放入最大堆中。堆的根将是最大的总和。

2.对于i从1到N： -将与第N-i列对应的堆节点的值减少N。 -新的最大列之和是堆的根加上i。

每次堆更新需要O(logn)，这导致O(n*logn)的总时间。

- interjay

我们如何找到对应于第n-1列的堆节点，这不会花费线性时间吗？ - 2147483647

1

@A.06 您可以拥有一个额外的数组，将列号映射到堆索引，并确保在移动堆节点时更新它。 - interjay

1

不，可以在数组中保留指向堆节点的指针以快速查找它们。 - Henry

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Henry · Accepted Answer

还有一种O(n)算法。和之前的答案一样，可以利用以下观察结果：

当你将第二行向左旋转（例如，将其从1,2,...,N更改为2,3,...,N,1）时，考虑列总和会发生什么变化：每个列总和都会增加1，除了一个列总和减少了N-1。

我们可以只减少一个列的总和而不是全部修改，然后取最大列总和再加1来找到新的列总和的最大值。因此，我们只需要更新一个列而不是所有列。

在迭代第二行可能的选择时，最大值出现的列只能向左移动或跳回总体最大的列。候选列是从左到右的最大扫描中的临时最大值所在的列。

1.计算第二行中第一个选择（1、2、...、N）的所有总和，并将它们存储在一个数组中。 2.在从左到右的扫描中，在该数组中查找最大值，并记住临时最大值的位置。 3.在从右到左的过程中，总和现在被减去了N。如果这个减少过程达到了max列，请检查数字是否小于overall maximum - N，在这种情况下，新的max列是overall maximum column，并将保持在循环的剩余部分。如果数字仍然大于步骤2中确定的先前最大值，则max列将在循环的剩余部分保持不变。否则，先前的最大值成为新的max列。

以输入7,1,6,2为例，算法运行如下：步骤1计算总和8,3,9,6 步骤2从左到右找到临时最大值：列1中的8，然后是列3中的9 步骤3通过从右到左遍历数组生成结果

8 3 9 6 -> output 9 + 0 = 9
8 3 9 2 -> output 9 + 1 = 10
8 3 5 2 -> current max col is decreased, previous max 8 is larger and becomes current
           output 8 + 2 = 10
8 -1 5 2 -> output 8 + 3 = 11

这是C语言中的算法：

#include <stdio.h>

int N;
int A[200000];
int M[200000];

int main(){
    int i,m,max,j,mval,mmax;

    scanf("%d",&N);

    for(i = 0;i < N; i++){
        scanf("%d",&A[i]);
        A[i] = A[i]+i+1;
    }

    m = 0;
    max = 0;
    M[0] = 0;

    for(i = 1;i < N; i++){
        if(A[i] > A[max]){
            m++;
            M[m] = i;
            max = i;
        }
    }

    mval = A[max] - N;
    mmax = max;

    for(i = N-1,j = 0;i >=0;i --,j++){
        printf("%d ", A[max]+j);

        A[i] = A[i] - N;

        if(i == max){
            if (A[i] < mval) {
                max = mmax;
            } else if(m > 0 && A[i] < A[M[m-1]]){
                max = M[m-1];
                m--;
            }
        }
    }

    printf("\n");

    return 0;
}