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

Question

这是我想解决的问题,

您将获得一个包含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,它存储到目前为止的最大值.
• 最大打印
• 循环遍历数组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的值可能非常大,所以N ^ 2时间太慢.
任何帮助将不胜感激.

Answer 1

还有一种O(n)算法.使用与之前答案中相同的观察结果:

现在考虑将第二行向左旋转时列的总和会发生什么变化(例如将其从1,2,...,N更改为2,3,...,N,1):每列总和将增加除了一列减少了N-1之外,它除以1.

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

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

1. 计算第二行(1,2,...,N)的第一个选择的所有总和并将它们存储在一个数组中.
2. find the maximum in this array in a left to right scan and remember the positions of temporary maxima.
3. in a right to left pass the sums are now decreased by N. If this decreasing process reaches the max column, check if the number is smaller than the overall maximum - N, in this case the new max column is the overall maximum column and it will stay there for the rest of the loop. If the number is still larger than the previous maximum determined in step 2, the max column will stay the same for the rest of the loop. Otherwise, the previous maximum becomes the new max column.

Taking the example input 7,1,6,2 the algorithm runs as follows: Step 1 calculates the sum 8,3,9,6 Step 2 finds the temporary maxima from left to right: 8 in col 1 and then 9 in col 3 Step 3 generates the results passing over the array from right to left

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