algorithm - 解决这个问题的更好方法是什么？

Question

这是我要解决的问题，

You are given a table with 2 rows and N columns. Each cell has an integer in it. The score of such a table is denfined as follows: for each column, consider the sum of the two numbers in the column; the maximum of the N numbers so obtained is the score. For example, for the table

7 1 6 2
1 2 3 4

the score is max(7 + 1; 1 + 2; 6 + 3; 2 + 4) = 9. The first row of the table is fixed, and given as input. N possible ways to ll the second row are considered:

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

For instance, for the example above, we would consider each of the following as possibilities for the second row.

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

Your task is to find the score for each of the above choices of the second row. In the example above, you would evaluate the following four tables,

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
and compute scores 9, 10, 10 and 11, respectively

Test data: N <= 200000
Time Limit: 2 seconds

这是一个显而易见的方法:

维护两个数组A，B，做如下n次

• 将每个元素 A[i] 添加到 B[i] 并保留一个变量 max，它存储到目前为止的最大值。
• 打印最大值
• 遍历数组 B[i] 并将所有元素加 1，如果任何元素等于 N，则将其设置为等于 1。

此方法将花费 O(n^2) 时间，外循环运行 N 次，并且有两个内循环，每个循环运行 N 次。

为了减少花费的时间，我们可以找到第一行的最大元素M(在线性扫描中)，然后每当A[i] + N <= M + 时删除A[i]和B[i] 1.
因为它们永远不会是最大值。

但这种方法在一般情况下可能表现更好，最坏情况下的时间仍然是 O(N^2)。

为了在常数时间内找到最大值我也考虑过使用堆，堆的每个元素都有两个属性，它们的原始值和要添加的值。但是对于 n 种情况中的每一种，它仍然需要线性时间来增加堆中所有元素的要添加的值。
所以时间仍然是 O(N^2)

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

Answer 1

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

Now consider what happens to the column sums when you rotate the second row to the left (e.g. change it from 1,2,...,N to 2,3,...,N,1): Each column sum will increase by 1, except for one column sum which is decreased by N-1.

Instead of modifying all the column sums, we can decrease the one column sum by N, and then take the maximum column sum plus 1 to find the new maximum of the column sums. So we only need to update one column instead of all of them.

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

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