AtCoder ABC 348 C - Colorful Beans (5Q, 灰色, 250 点)

連想配列のいい練習問題！

• 問題へのリンク

問題概要

種類のビーンズがあって、 種類目のビーンズはおいしさが で色が である。ビーンズは混ぜられており、色でしか区別することができない。

あなたはビーンズの色を 1 つ選び、その色のビーンズをどれか 1 粒食べる。ビーンズの色をうまく選ぶことで、食べる可能性のあるビーンズのおいしさの最小値を最大化せよ。

制約

• 
• 

考えたこと

まず、問題文の意味を理解するのが少し大変かもしれない。まず前提として、ある色 のビーンズを食べると決めたとき、その色のビーンズ同士は区別できないので、最悪の場合には「その色の中で美味しさが最小のビーンズを食べることになる」という可能性を考える必要があるのだ。

そして今回の問題が要求しているのは、そのような「その色のビーンズの美味しさの最小値」を、色ごとに見ていったときの最大値を求めよ、ということなのだ。

そこで、次のような連想配列（C++ ならば map<int,int> 型）を構築しよう。

---

• ma[c] ← 色 のビーンズの美味しさの最小値

---

このような連想配列を構築したあとは、キーをすべて見て、その値の最大値をとればよい。

計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    map<int, int> ma;
    for (int i = 0; i < N; i++) {
        int A, C;
        cin >> A >> C;
        if (ma.count(C)) ma[C] = min(ma[C], A);
        else ma[C] = A;
    }

    int res = 0;
    for (auto [key, val] : ma) res = max(res, val);
    cout << res << endl;
}