[1903号:パズルゲーム]-Sliver 2

質問する

質問リンク
石煥は子供だ.小石煥は自然数が書かれたカードを持っていろいろなゲームをするのが好きだ.今日、錫煥さんはどんなゲームをしていますか.パズルゲームだ!
小石煥は自然数と書かれたカードをn枚持っている.最初はi番カードにaiと書いてありました.トランプゲームとは、これらのカードを組み合わせて遊ぶゲームです.クレジットカードの組み合わせは、次の手順で構成されます.
1.x番カードとy番カードを選択し、2枚のカードに書かれた数字の加算値を計算します.(x ≠ y)
2.計算された値をx番カードとy番カードの2枚を上書きします.
このカードをm回合わせると、ゲームは終了します.m次合体が完成した後、n枚のカードの数字を足した値がこのゲームの点数です.この点数を最小にするのがゲームの目標です.
小石煥は数学が好きだが、まだ子供なので点数をどれだけ低く下げられるか分からない(大人の石煥はもちろん分かりやすい).そこで、問題解決能力に優れた方々にお願いします.最小スコアを計算するプログラムを作成しましょう.

入力

第1行目のカードカウントを示すn(2≦n≦1000)と、何回のカード合体を表すm(0≦m≦15)である.×n).
2行目では、n個の1枚目のカード状態を表す自然数a 1,a 2,...,anがスペースに分割される.(1 ≤ ai ≤ 1,000,000)

しゅつりょく

最初の行で作成できる最小スコアを出力します.

方法

2つの解法がある.
1つ目の方法は、コンビネーションカードを配列するたびにソートします.
2つ目の方法は、優先キューを使用します.

コード(第1の方法)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n,m;
    static long[] card;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        card = new long[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            card[i] = Long.parseLong(st.nextToken());
        }
        for(int i=0; i<m; i++){
            Arrays.sort(card);
            long cardA = card[0];
            long cardB = card[1];
            card[0] = cardA+cardB;
            card[1] = cardA+cardB;
        }
        long sum = 0L;
        for(int i=0; i<n; i++){
            sum += card[i];
        }
        System.out.println(sum);
    }
}

コード(第2の方法)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n,m;
    static long[] card;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        card = new long[n];
        PriorityQueue<Long> pq = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            card[i] = Long.parseLong(st.nextToken());
            pq.add(card[i]);
        }
        for(int i=0; i<m; i++){
            long cardA = pq.poll();
            long cardB = pq.poll();
            pq.add(cardA+cardB);
            pq.add(cardA+cardB);
        }
        long sum = 0L;
        while(!pq.isEmpty()){
            sum += pq.poll();
        }
        System.out.println(sum);
    }
}

と知る

和を求め始めたばかりの頃は変数タイプをint型にあげていましたが、結果は間違っていました.
最初はタイプ設定が間違っているのではなく、コードが間違っていると思っていたので、ずっと悩んでいました.もう一度問題を見てみると、最悪の場合はint型の範囲を超えていることがわかりました.
だからlongに変えて提出した答えは正しい!!
指定された条件や入力値の範囲に注意してください!!