c - SPOJ : The day of the competitors

Question

我正在尝试解决问题 SPOJ 上的比赛日.我尝试了以下方法:

我正在寻找最好的初始玩家，所以最初排名第一的玩家是最好的。在此之后我遍历所有玩家并为他们每个人尝试查看当前最好的玩家中是否有比这更好的，如果是这样那么这不是很好丢弃它(因为存在一些比这更好的玩家)，否则我将其添加到最佳播放器列表中。最后我会输出最佳玩家的数量。

    for(i=0; i<num; i++)
    {
        for(j=0; j<ctr; j++)
        {               
            // i is already in best
            if(i == best_n[j])
                break;                        
            if((elmts[i].a < elmts[best_n[j]].a) ||
                    (elmts[i].b < elmts[best_n[j]].b) ||
                    (elmts[i].c < elmts[best_n[j]].c))
            {
                continue;
            }
            else
            {
                break;
            }
        }
        if(j>=ctr)
        {
            best_n[ctr] = i;
            ctr ++;
        }
    }

num 是玩家数量，ctr 是目前最佳数组中的玩家数量。但我得到一个错误的答案。我试图再次运行一个循环来验证是否有任何球员比其他球员差，但这也会导致错误的答案。此外，我认为我的方法效率不高，在最坏的情况下为 n^2。你能帮我找出我的错误吗？我该如何改进它以使其更有效率。

Answer 1

看到的一个问题是您的算法需要删除 best_n 中当前优于的所有元素。

考虑:

1 5 5 // inserted into best at start
5 1 1 // inserted into best at start
3 4 4 // not worse than any of the above, insert into best
4 3 3 // not worse than any of the above, insert into best
2 2 2 // better than 3 4 4 and 4 3 3

(伪)代码看起来像这样:(如果当前在每场比赛中都更好，我们必须用当前替换另一个)

// define '<' as 'better than'
if (not best[j] < elmts[i])
  if (elmts[i] < best[j])
    remove best[j]
    ctr--
  continue
else break

高效解决方案:

O(n^2) 可能太慢了。 Here是对高效解决方案的高级概述。 Here是可能有效的 C++ 代码。