プライオリティキューを使用して無制限ゲームを実装しますか？

Question

子供のグループはUnMonopolyと呼ばれるゲームをしたいと思っています。最も多くのお金を払ったプレイヤーは、お金の半分を最も少ない金額でプレイヤーに渡す必要があります。ターンが完了した後、最も高い金額の人を勝者として発表する。ターン数と選手数を取ってこのゲームを実装します。 （ヒント：使用優先度キュー）

サンプル入力：選手の

数：nはターンの

番号：

：メートル

が

出力各選手の詳細とお金を入力します。

受賞者：プレーヤー名

これは私の質問です。私はコードを書いています。これは実装する正しい方法ですか、それに欠陥がありますか？より少ない時間の複雑さでより良い実装がありますか？あなたがプライオリティキューに各ターンを再作成するため

ここ

私のコードは、

import java.util.*; 

class Player implements Comparator<Player> { 

    String name; 
    int money; 
    Player(String name, int m) { 
     this.name = name; 
     money = m; 
    } 
    public Player() { 
     this.money = 0; 
     this.name = null; 
    } 

    public String toString() { 
     return "NAME: "+name+"\nMONEY: "+money; 
    } 

    public int compare(Player p1, Player p2) { 
     return p2.money - p1.money; 
    } 
} 

public class Unmonopoly { 

    public static void main(String[] args) { 

     Player pl = new Player(); 
     Stack<Player> pla = new Stack<Player>(); 
     Scanner sc = new Scanner(System.in); 
     System.out.println("Enter the number of players: "); 
     int n = sc.nextInt(); 

     PriorityQueue<Player> play = new PriorityQueue<Player>(n,pl); 
     System.out.println("Enter player details: "); 

     for(int i = 0; i < n; i++) { 
      Player p = new Player(sc.next(),sc.nextInt()); 
      play.add(p); 
     } 

     for(Player p: play) { 
      System.out.println("Name: "+p.name+"\nMoney: "+p.money); 
     } 

     System.out.println("\nEnter the number of turns: "); 
     int turns = sc.nextInt(); 
     for(int i = 0; i < turns; i++) { 
      Player max = play.peek(); 
      max.money = max.money/2; 
      while(!play.isEmpty()) { 
       pla.push(play.peek()); 
       play.remove(); 
      } 
      Player min = pla.pop(); 
      pla.push(min); 
      System.out.println("Player with min money is: \n"+min); 
      min.money = min.money + max.money; 
      while(!pla.isEmpty()) { 
       play.add(pla.peek()); 
       pla.pop(); 
      } 
     } 
     sc.close(); 
     System.out.println("**************WINNER************** \n\n\tNAME: "+play.peek().name+"\n\tMONEY: "+play.peek().money); 
    } 
} 

Answer 1

あなたの複雑さは、O（N * Mは*ログ（N））です。

各ターンで最小と最大の両方のプレイヤーが必要なので、ヒントがどれほど有効かわからないので、より良いデータ構造がTreeSetになる可能性があります。

for (int i = 0; i < turns; i++) { 
    Player min = players.pollFirst(); 
    Player max = players.pollLast(); 

    min.money += max.money/2; 
    max.money -= max.money/2; 

    players.add(min); 
    players.add(max); 
} 

両方poll操作ならびにaddはO（ログ（ある：複雑さは、そのような場合には、メインループは、単純であろうO（M *ログ（N））..

あろうN））..