0

私は問題を解決しようとしています。SPOJの競合他社の日。私は次のアプローチを試しました：

私は最高のイニシャルプレイヤーを探しているので、最初は1位のプレイヤーが最高です。この後、私はすべてのプレーヤーを繰り返し、それぞれについて、現在の最高のプレーヤーのいずれかがこれよりも優れているかどうかを確認しようとします。そうであれば、これは優れていません（これよりも優れたプレーヤーが存在するため）。最高のプレーヤーリストに追加されます。最後に、最高のプレーヤーの数を出力します。

    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

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)遅すぎる可能性があります。以下は、効率的なソリューションの概要です。これは、おそらく動作する C++ コードです。

于 2013-02-06T18:35:16.793 に答える