[アルゴリズム]配列白駿1715カード
0、問題
きちんとした数字カードが2束あると言ってください.1束あたりのカードの数をA、Bと言います.普通は2束を合わせて1つ作って、A+Bの比較をします.例えば、20枚のデジタルカードと30枚のデジタルカードの組み合わせを50回比較する必要がある.
多くのデジタルカードが机の上に縛られている.2束に分けると、選択順によって比較回数が大きく異なります.例えば、10枚、20枚、40枚のギフトバッグがあれば、10枚と20枚のギフトバッグを合わせ、30枚のギフトバッグと40枚のギフトバッグを合わせて(10+20)+(30+40)=100回の比較が必要です.しかし10枚と40枚を合わせた後、50枚と20枚を加えると(10+40)+(50+20)=120回の比較が必要なので非効率的な方法です.
N個のデジタルカードグループの各時間を指定すると、少なくとも何回の比較が必要かを求めるプログラムを作成します.
入力
1行目はNです.(1≦N≦100000)は、N行においてデジタルカード群の各サイズを与える.デジタルカードグループのサイズは1000以下の整数です.
しゅつりょく
1行目に最小比較回数を出力します.
1.アイデア
💡 数字の和を最小にしなければならない
💡 2つの最小の数を加えて、加算して、並べ替えて、2つの最小の数を取り出して繰り返します.
💡 Priority Queueの使用
2.コア解答
1)最小数を2個加算
int a = pq.poll();
int b = pq.poll();
sum += (a+b);
2)優先順位キューのソートpq.add(a+b);
3.コード
import java.io.*;
import java.util.*;
public class Greedy_16 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for(int i=0; i<n; i++)
pq.add(Integer.parseInt(br.readLine()));
int sum = 0;
while(pq.size() > 1){
int a = pq.poll();
int b = pq.poll();
sum += (a+b);
pq.add(a+b);
}
System.out.println(sum);
}
}
4.結果
成功
最初は並べ替えだと思っていたが、最初から最後まで合わせておけばよかった.(10,15,20,25,30)などの反例😭
Reference
この問題について([アルゴリズム]配列白駿1715カード), 我々は、より多くの情報をここで見つけました https://velog.io/@kha0318/Algorithm-백준-1715-카드-정렬하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol