【AtCoder】ABC 448 B - Pepper Addiction

2026-03-16

AtCoder/ABC/B問題 AtCoder/ABC/200点問題 AtCoder/灰Diff AtCoder/NoviSteps/5Q AtCoder/アルゴリズムの基礎/forループ競技プログラミング

B - Pepper Addiction

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 68 / NoviSteps: 5Q / 配点: 200 点

問題概要

$M$ 種類のコショウがレストランに置いてあり、種類 $j$ のコショウは $C_j \mathrm{\, [g]}$ ある。

高橋君はこの店で $N$ 個の料理を注文した。相性の都合で $i$ 番目の料理には種類 $A_i$ のコショウしかかけることができず、 $i$ 番目の料理にかけられるコショウの量の上限は $B_i \mathrm{\, [g]}$ である。なお、種類 $j$ のコショウを合計 $C_j \mathrm{\, [g]}$ を超えてかけることはできない。

高橋君が料理にかけたコショウの量の合計を最大にしようとするとき、合計何 $\mathrm{g}$ のコショウを料理にかけることができるか求めよ。

制約

入力は全て整数
$1 \le N,M \le 1000$
$1 \le A_i \le M$
$1 \le B_i,C_i \le 10^6$

考察

料理 $i$ について、かけることのできるコショウの最大量は $v_i = \min(B_i, C_{A_i})$ である。

したがって、全ての料理に対して $v_i$ を求めて合計すればよい。

ただし、料理 $i$ に $v_i \mathrm{\, [g]}$ のコショウをかけたとき、残りのコショウの量を $C_{A_i} \leftarrow C_{A_i} - v_i$ と更新しておくことを忘れないようにする。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int N, M;
11.    cin >> N >> M;
12.    vector<int> C(M);
13.    rep(i, 0, M) cin >> C[i];
14.    vector<int> A(N), B(N);
15.    rep(i, 0, N) cin >> A[i] >> B[i], A[i]--;
16. 
17.    int ans = 0;
18.    rep(i, 0, N)
19.    {
20.        int v = min(B[i], C[A[i]]);
21.        ans += v;
22.        C[A[i]] -= v;
23.    }
24. 
25.    cout << ans << endl;
26. 
27.    return 0;
28.}