白駿-整列カード[1715]

5554 ワード
アルゴリズム#アルゴリズム# Java ツールバーの グリディ テキストリンク

質問する


サマリ
  • N個のデッキ
  • は、例える、所与のカード群A,Bが1つとなるように、A+B回比較
    • を行う必要がある.
  • N個の与えられたカードのグループを求めて少なくとも何回
    • 比較する必要があります

    入力


    1行目はNです.(1≦N≦100000)は、N行においてデジタルカード群の各サイズを与える.デジタルカードグループのサイズは1000以下の整数です.

    しゅつりょく


    1行目に最小比較回数を出力します.

    に答える


    最小値に達するには、昇順にソートし、小さい頃から計算を開始します.この場合は優先キューを使用します.
    優先度キューは、通常のキューとは異なり、優先度の高いキューを先に取り出す構造です.内部構造は臀部からなり,時間複雑度はO(NlogN)O(NlogN)O(NlogN)であった.
    再び問題に戻った場合、指定したカードグループを優先順位キューに入れ、2つ取り出し、合計すればよい.

    ソース

    import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

		for (int i = 0; i < n; i++) {
			pq.offer(sc.nextInt());
		}
		int result = 0;

		while (pq.size() != 1) {
			int a = pq.poll();
			int b = pq.poll();

			int sum = a + b;

			result += sum;
			pq.offer(sum);
		}

		System.out.println(result);

	}

}
    String, StringBuffer, StringBuilder
    [JS]オブジェクト向けプログラミングとは?