概要

各製品について、内部温度が閾値 \(T\) 以上の場合に限り、追加冷却処理（コスト \(C\)）か不良品出荷（損失 \(D\)）のどちらかを選択し、合計コストを最小化する問題です。

考察

各製品は独立に扱うことができます。内部温度が \(T\) 未満の製品は不良品にならないため、何もしなくてもコストは発生しません。内部温度が \(T\) 以上の製品については、追加冷却処理を施す（コスト \(C\)）か、そのまま出荷して損失 \(D\) を被るかのどちらかを選べます。したがって、各製品について \(C\) と \(D\) の小さい方を選べば良いことになります。

アルゴリズム

1. 各製品の内部温度 \(W_i\) を順に確認します。
2. \(W_i < T\) の場合、コストは発生しません。
3. \(W_i \geq T\) の場合、\(\min(C, D)\) を合計コストに加算します。

このアルゴリズムは、各製品を一度だけ見れば良いため、非常に効率的です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力データの読み込みを除く）

実装のポイント

• 入力の読み込み後、各製品の温度をループで処理します。

• 条件分岐は単純で、\(W_i \geq T\) のときのみ \(\min(C, D)\) を加算します。

• 内部温度が \(T\) 未満の場合は何もせずスキップします。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    T = int(data[1])
    C = int(data[2])
    D = int(data[3])
    W_list = list(map(int, data[4:4+n]))
    
    cost_if_cool = C
    cost_if_not = D
    
    total_cost = 0
    for w in W_list:
        if w >= T:
            if cost_if_cool < cost_if_not:
                total_cost += cost_if_cool
            else:
                total_cost += cost_if_not
        else:
            pass
    
    print(total_cost)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。