2名队员知道最大移动

Question

给出了一个名单的N名球员谁要玩一个2人的游戏。他们中的每一个人要么很擅长做一个特定的动作，要么就不是。找出一个2人团队所能知道的最大移动次数。

还要找出有多少队能知道最大的移动次数？

假设我们有4名玩家，如果ai是1，则有5次移动，如果ai为1，则为0。

10101
11100
11010 
00101

在这里，一个2人团队可以知道的最大移动数是5，他们的两个队可以知道最大的移动次数。

解释：(1，3)和(3，4)知道所有的5个动作。所以，2人队知道的最大移动是5，只有2支球队能做到这一点。

My approach：对于每一对玩家，我检查是否有任何一位球员精通这一移动，对于每一位玩家，他用他的本地最大移动组合来保持他与其他玩家所能做的最大对。

vector<int> pairmemo;
for(int i=0;i<n;i++){
    int mymax=INT_MIN;
    int countpairs=0;
    for(int j=i+1;j<n;j++){
        int count=0;
            for(int k=0;k<m;k++){
                if(arr[i][k]==1 || arr[j][k]==1)
                {
                    count++;
                }
        }
        if(mymax<count){
            mymax=count;
            countpairs=0;
        }
        if(mymax==count){
            countpairs++;
        }

    }
    pairmemo.push_back(countpairs);
    maxmemo.push_back(mymax);
}

所有N个玩家的总体最大值是答案，计数是正在计算的对的对应和。

for(int i=0;i<n;i++){
    if(maxi<maxmemo[i])
        maxi=maxmemo[i];
}

int countmaxi=0;

for(int i=0;i<n;i++){
    if(maxmemo[i]==maxi){
        countmaxi+=pairmemo[i];
    }
}

cout<<maxi<<"\n";
cout<<countmaxi<<"\n";

时间复杂度: O((N^2)*M)

代码:我如何改进它？

约束: N<= 3000和M<=1000

Answer 1

如果你用一个非常大的整数来表示每一组移动，问题归结为找到在MovesI OR MovesJ中有最大位数的一对玩家(I，J)。

因此，您可以使用位-包装和压缩的所有信息的移动在长整数数组.按照约束存储需要16个无符号的长整数。因此，对于每一对玩家，您OR对应的数组和计数的数量。这需要O(N^2 * 16)，它在约束条件下运行得相当快。

示例:假设给定的矩阵是

11010
00011

你用4位整数来包装它。看起来应该是：

1101-0000
0001-1000

那是,

13,0
1,8

在OR之后，2人队的移动数组变成13,8，现在计算其中的位数。您还必须优化位数的计算，这样才能读取可接受的答案here，否则因素M就会出现复杂性。在处理这些对时，只需维护一个计数变量和一个maxNumberOfBitsSet变量。

Answer 2

我要做的是: 1.在所有可能的对( O(N^2) )之间执行逻辑或或，并将它的和存储在一个忽略对称对角线的2D数组中。2.在2D数组中找到最大值(在执行任务1时可以完成) -> O(1) 3.计算2D数组中的单元格数等于任务2 O(N^2)中的最大值

总和：2*O(N^2)+ O(1) => O(N^2)

示例(使用问题中的数据(带有字母索引)：

 A[10101] B[11100] C[11010] D[00101]

任务1：

[A|B] = 11101 = SUM(4)
[A|C] = 11111 = SUM(5)
[A|D] = 10101 = SUM(3)
[B|C] = 11110 = SUM(4)
[B|D] = 11101 = SUM(4)
[C|D] = 11111 = SUM(5)

任务2(完成时完成1)：

Max = 5

任务3：

Count = 2

顺便说一句，O(N^2)是最小可能的，因为你必须检查所有可能的对。

Answer 3

因为你必须找到所有的解决方案，除非你找到一种方法来找到一个计数，而不实际地找到解决方案本身，你必须实际地查看或消除所有可能的解决方案。所以最坏的情况总是O(N^2*M)，我称之为O(n^3)，只要N和M都是大的和相似的大小。

但是，您可以希望通过剪枝在一般情况下获得更好的性能。别检查每一个案子。找出消除组合而不检查它们的方法。

我将对每个玩家已知的移动总数进行求和和存储，并按该值对数组行进行排序。这应该为尽早退出循环提供了一个简单的检查。O(n log n)的排序在O(n^3)算法中基本上是自由的。

使用Priyank的基本思想，除了与位集，因为你显然不能使用一个固定的3000位整数类型。

您可能会从为列创建第二个位集数组中获益，并将其用作修剪播放机的掩码。