次の問題を解決するために疑似コードを作成しようとしています。
入力: バスケットボールの試合の n チーム。各チームの Ti、Tj がプレーし、その勝敗記録は行列 A にあります
(i < j の場合、Ti が Tj に勝った場合、A[i, j] = 1)。
チームは 10 回以上負けなければメダルを獲得します。
出力: メダルを受け取るすべてのチーム。O(n) 時間で見つけます。
これはこれまでの私の疑似コードです。現時点では疑似コードで十分ですが、これが正しく機能するとも、線形時間で実行されるとも思いません。
//input: matrix A of win/losses
//output: list of teams with medals
set S to an array of length n, with value 0 for all indices //keeps track of number of losses
for each team:
for each game played in the team's row in M:
if the team won:
increment the opponent’s number of losses in the opponent’s index of S
else:
increment the team's number of losses in team's index of S
if at any point a value in the array S reaches 11, remove that team from the list of teams we consider //so basically ignore all the games they play from hereon out
end for loop
end for loop
take this new potential list of teams with medals
iterate through each team's row in M, counting losses //to check if they lost against any of the teams we removed from the previous for loop
if losses > 10, remove the team from list
return final list
qwertyman のアプローチに基づいてO(n)、次のようにこれを解決できます。
残りのチームのすべての可能なマッチアップをループする
O(n²)に見えるかもしれませんが、残りのチームの数は、これにかかるのに十分な速さで減少しますO(n)。11*n(損失カウントが 11 になると、それを考慮から除外し、それ以上増やさないためです)。ループは最大で11*n=O(n)回実行されます。これで、最大で 21 チームが残ります。
これは、すでに削除されたチームに対する残りのチームの損失を認識していない場合 (これが最良のケースであることが簡単にわかります)、残りの各チームが残りの 20 チームのうち 10 チームに対して勝利した場合です。22 チームは不可能です。各チームは、10 以下の損失を維持するために少なくとも 11/21 試合に勝利する必要があり、負けよりも多くの勝利につながるためです。
残りの各チームについて、そのチームのすべてのゲームを単純に実行して、負けの数 ( O(n)= の21 ループO(n)) を数え、10 回以下の負けのチームを出力します。
Java ライクなコード: (読みやすくするために作業バージョンを少し変更)
// returns true if i beat j or false if j beat i
boolean beat(int i, int j);
// return the loser in the game between i and j
int loser(int i, int j);
// swaps i with the last element in indices and decreases index count, takes O(1)
void removeIndex(int i);
// x = indices[y] corresponds to a remaining team x
int[] indices = new int[n];
// number of elements in indices, decreased in removeIndex
int indicesCount = n;
// initialise our array of indices
for (int i = 0; i < n; i++)
indices[i] = i;
// initialise our array of losses
losses = new int[n];
// loop over all possible match-ups and eliminate (some) teams with > 10 losses
for (int a = 0; a < indicesCount; )
{
for (int b = a+1; losses[indices[a]] <= 10 && b < indicesCount; )
{
losses[loser(indices[a], indices[b])]++;
if (losses[indices[b]] > 10)
removeIndex(b);
else
b++;
}
if (losses[indices[a]] > 10)
removeIndex(a);
else
a++;
}
// find teams with <= 10 losses
for (int i = 0; i < indicesCount; i++)
{
int lossCount = 0;
for (int j = 0; j < n; j++)
if (indices[i] == j)
continue;
else if (beat(j, indices[i]))
lossCount++;
if (lossCount <= 10)
// output indices[i]
}
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加