公式

B - 買い物リスト / Shopping List 解説 by MMNMM


この問題では、それぞれの日に買うことができる食材のうち

  • 値段が最も安い野菜
  • 値段が最も安い肉類

が存在するかどうかと、存在するならそれらの値段を求められればよいです。 これらが存在すれば、求める価格の最小値はこれらの値段の合計になります。

最も安い野菜(もしくは肉類)の値段を求めるには、その日に買うことができる食材を順に見て「これまでに見た中で最も安い野菜(もしくは肉類)の値段」を管理するのがよいでしょう。 初期値、つまり「これまで見た食材に野菜(もしくは肉類)がない」ことを表す値は食材の値段としてありえない値であれば何にしてもかまいません(\(0\) や \(-1\) 、Nonestd::nullopt"empty" など)が、今回の問題では \(10 ^ {10}\) などの食材の値段としてありえる値より大きい値にすると実装が楽になる場合があります。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> foodstuffs(N);
    for (auto& [P, T] : foodstuffs)
        cin >> P >> T;

    for (int i = 0; i < M; ++i) {
        int K;
        cin >> K;

        int lowest_vegetable_price = 1000000001; // 食材の値段より高くしておく
        int lowest_meat_price = 1000000001;
        for (int j = 0; j < K; ++j) { // それぞれの食材について
            int S;
            cin >> S;
            auto [P, T]{foodstuffs[S - 1]};
            if (T == 0) { // 野菜なら
                lowest_vegetable_price = min(lowest_vegetable_price, P); // 野菜の値段を更新
            } else { // 肉類なら
                lowest_meat_price = min(lowest_meat_price, P); // 肉類の値段を更新
            }
        }

        if (lowest_vegetable_price == 1000000001 || lowest_meat_price == 1000000001) { //  どちらかの食材がなければ
            cout << -1 << endl; //  -1 を出力
        } else { //  どちらもあれば
            cout << lowest_vegetable_price + lowest_meat_price << endl; // 合計金額を出力
        }
    }
    return 0;
}
N, M = map(int, input().split())

food_stuffs = [tuple(map(int, input().split())) for _ in range(N)]

for _ in range(M):
    K, *S = map(int, input().split())
    
    lowest_vegetable_price = 10 ** 10 # 食材の値段より高くしておく
    lowest_meat_price = 10 ** 10
    for s in S:
        P, T = food_stuffs[s - 1]
        if T == 0: # 野菜なら
            lowest_vegetable_price = min(lowest_vegetable_price, P) # 野菜の値段を更新
        else: # 肉類なら
            lowest_meat_price = min(lowest_meat_price, P) # 肉類の値段を更新

    if lowest_vegetable_price == 10 ** 10 or lowest_meat_price == 10 ** 10: # どちらかの食材がなければ
        print(-1) # -1 を出力
    else: # どちらもあれば
        print(lowest_vegetable_price + lowest_meat_price) # 合計金額を出力

投稿日時:
最終更新: