解决这个问题的更好方法是什么?

Question

这就是我想解决的问题，

给定一个2行N列的表。每个单元格中都有一个整数。分数这样一个表的定义如下:对于每一列，考虑两个数字的和在列中;这样得到的N个数的最大值就是分数。例如，对于表

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

你的任务是找出上述第二行每个选项的得分。在在上面的例子中，您将计算以下四个表，

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]。
因为它们永远不会是max。

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

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

我无法找到比N^2时间更快解决这个问题的方法，因为N的值可能非常大，所以速度太慢了。
任何帮助都将非常感激。

Answer 1

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

现在考虑当你向左旋转第二行时，列和会发生什么(例如从1,2，…，N到2,3，…，N,1):每个列和增加1，除了一个列和减少N-1。

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

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

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

以输入7,1,6,2为例，算法运行如下:步骤1计算和8,3,9,6步骤2从左到右找到临时最大值:col1为8,col3为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;
}

Answer 2

以下是O(n*logn)的解决方案:

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

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

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

所以我们的算法是:

• 设置第二行为1,2，…，N，计算每列的和。把所有这些和放到一个最大堆里。

• For i in 1 to N:

  • 将N-i列对应的堆节点的值减少N。
  • 新的最大列和是堆的根加上i。

每个堆更新占用O(logn)，导致O(n*logn)的总时间