白俊解答-ギターライン1049号

📜 問題を理解する
DayOf Morningのギタリスト江土が使っていたギターがN本の弦を切った.そのため、新しい行を購入または交換する必要があります.疆土はできるだけお金を少なくします.6行セットを買うこともできますし、1つ以上の単行セットを買うこともできます.
1つのプログラムを作成して、プログラムの中で切れた他の行数Nと他の行ブランドM個、各ブランドが販売する他の行数6個のパッケージの価格、および単独で購入する時の価格を与える時、少なくともN個を買うのに最小限のお金がかかります.
💡 問題の再定義
各ブランドごとに6つのコース価格と1つのコース価格がある場合は、切れた他のロープを最低価格で購入します.
▼▼▼計画作成
まず、各パッケージと単一価格の中で最も安い価格を格納します.
その後、小包だけで詐欺、小包、ばら積み詐欺をすべて算出し、その中で最も安い金額を印刷することができます.
💻 計画の実行

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int N, M, package_price, piece_price;
    cin >> N >> M;
    double min_price = 1001 * N;
    int min_package_price = 1001, min_piece_price = 1001;
    int package_num, piece_num;

    for(int i=0; i<M; i++){
        cin >> package_price >> piece_price;
        if (package_price < min_package_price)
            min_package_price = package_price;
        if (piece_price < min_piece_price)
            min_piece_price = piece_price;
    }

    // 패키지만으로 사기
    package_num = ceil(N / 6.0);
    if(package_num * min_package_price < min_price)
        min_price = package_num * min_package_price;

    // 패키지 + 낱개
    package_num = floor(N / 6.0);
    piece_num = N % 6;
    if(package_num * min_package_price + piece_num * min_piece_price < min_price)
        min_price = package_num * min_package_price + piece_num * min_piece_price;

    // 낱개만으로 사기
    if(min_piece_price * N < min_price)
        min_price = min_piece_price * N;

    cout << min_price << endl;
}

🤔 振り返る
最も安い金額を出力するために、グリディアルゴリズムを採用しました.現在の条件下で最適値を探す問題であるため,グリディアルゴリズムが適切である.