0

我正在努力解决问题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。你能帮我弄清楚我的错误吗，我该如何改进它以提高效率。

4

1 回答 1

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) is likely too slow. Here is a high-level overview of an efficient solution. Here is C++ code which presumably works.

于 2013-02-06T18:35:16.793 回答