7

私は次の問題で遊んでいて、力ずくのアプローチをとっていましたが、良い解決策を思いつくことができませんでした。問題は次のとおりです。

2*N 枚のカードがあります。あなたとあなたの対戦相手はそれらを分割します（あなたにN枚のカード、それらにN枚）。彼らが持っているカードと、それらをプレイする順番を正確に知っています。

ゲームのルールは次のとおりです。最初の N/2 ラウンドでは、最も高いカードを持つ人が勝ち、最後の N/2 ラウンドでは、最も低いカードを持つ人が勝ちます。

これらのルールと、対戦相手がカードをプレイする順序を考えると、獲得できる勝利の最大額はいくらか.

例：

あなたはカードを持っています: 2, 5, 6, 7. 対戦相手はカードを持っています: 1, 8, 4, 3 そして、それらを順番にプレイします.

7 対 1 でプレイし、2 ラウンド目と 3 ラウンド目で負け、最終ラウンドで 2 をプレイして勝つため、獲得できる最大スコアは 2 です。

私の考え: カードを 2 つの山に分けます。数字の大きい方と小さい方です。次に、最適なマッチングを見つけます。

疑似コード/アルゴリズムのアイデアは大歓迎です。

編集: 合計 N ラウンドがあります。最初の N/2 ラウンド: 高いカードが勝ちます。最後の N/2 ラウンド: 下のカードが勝ちます。N は偶数でなければなりません。

4

2 に答える 2

2

私は提案します：

  • カードを 2 つの山に分割します。
  • それらを並べ替える
  • 対戦相手のより大きなカードを値で並べ替える (最初のラウンド)
  • 対戦相手のカードの最大から下へ:
    残りの最大値が対戦相手のカードよりも低い場合は、最低のカードをプレイ (負け)
    、そうでない場合は最高のカードをプレイ (勝利)

下のパイルについても同様で、順序を逆にします。

于 2015-12-14T00:37:46.463 に答える
1

まず、N 個のアイテム (ラウンドごとに 1 つ) の配列を作成します。各項目は、そのラウンドの「勝利カード」のリストです。つまり、そのラウンドに勝利するカードのセットです。あなたの例では、{{2567},{},{2},{2}}.

次のリストは、カードをラウンドに「割り当てる」必要があるいくつかの状況を示しています。これは、そのラウンドでそのカードをプレイすることを決定し、その後は何も変更できないことを意味します。カードが割り当てられた後、割り当てられたラウンドをラウンドのセットから削除し、割り当てられたカードを任意のラウンドの勝利カードのセットから削除した後、アルゴリズムを続行する必要があります。

どのような状況でもこれらのルールのいずれかを適用しても、可能な勝利の数が減ることはないことは明らかであるため、ブルートフォースを開始する前に可能な限りルールを適用することは常に良い考えです.

  • カード C がラウンド R に勝つことができ、カード C が他のラウンドに勝つことができない場合、カード C をラウンド R に割り当てます。
  • カード C がどのラウンドでも勝てず、ラウンド R がどのカードでも勝てない場合、カード C をラウンド R に割り当てます。
  • カード C が最初の N/2 ラウンドのいくつかで勝つことができるが、カード C が最後の N/2 ラウンドのいずれでも勝つことができず、カード C がこの特性を持つ最も高いカードである場合、カード C を次のように割り当てます。それが勝つ最も困難なラウンド (つまり、カード C が勝つ対戦相手のカードの中で最も高いもの)。
  • カード C が最後の N/2 ラウンドのいくつかで勝つことができるが、カード C が最初の N/2 ラウンドで勝つことができず、カード C がこの特性を持つあなたのカードの中で最も低い場合、カード C をそれが勝つ最も難しいラウンド (つまり、カード C が勝つ対戦相手のカードの中で最も低いもの)。

カードをラウンドに割り当てると、ラウンドと各ラウンドで勝つカードの両方が変わるため、これらのルールのいずれかが適用されなくても、他のルールを適用すると適用される可能性があることに注意してください。そのため、それらすべてを完全に繰り返しても新しい割り当てが生成されなくなるまで、繰り返し試行する必要があります。

これは決定的な解決策ではありませんが、最終的な力ずくのステップがはるかに容易になることは間違いありません。

于 2015-12-14T00:56:17.777 に答える