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个；: : : ; ; 氮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 来存储迄今为止的最大值。
  • 打印最大值
  • 遍历数组 B[i] 并将所有元素加 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 的值可能非常大，这将太慢。
任何帮助将不胜感激。

4

2 回答 2

6

还有一个 O(n) 算法。使用与先前答案相同的观察结果：

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

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

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

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

以输入 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;
}
于 2012-12-26T13:53:40.537 回答
2

这是一个O(n*logn)解决方案：

假设您计算第二行的特定排列的所有列总和。

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

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

所以我们的算法是：

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

  • 对于i1 到N:

    • N-i将第 th 列对应的堆节点的值减小N.
    • 新的最大列总和是堆的根 plus i。

每次堆更新都会O(logn)导致O(n*logn)总时间。

于 2012-12-26T13:14:32.000 回答