【AtCoder】ABC 348 C - Colorful Beans | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 156

問題概要

種類のビーンズが一つずつあり、 種類目のビーンズはおいしさが で色が である。ビーンズは色でしか区別することができない。これからビーンズの色を1つ選び、その色のビーンズをどれか1粒食べる。ビーンズの色をうまく選ぶことで、食べる可能性のあるビーンズのおいしさの最小値を最大化したい。食べる可能性のあるビーンズのおいしさの最小値の最大値を整数として出力せよ。

制約

• 入力はすべて整数。
• 
• 

考察

「最小値を最大化する」と言われると混乱するが、やるべきことをまとめるとこんな感じ。

1. 色ごとにビーンズのおいしさをまとめ、その最小値を記録しておく。
2. 全ての色を見ていき、「記録されたビーンズの最小値」の最大値を求める。

色ごとのビーンズのおいしさの記録は、色をkey、おいしさの最小値をvalueとするmapを使うのが良いだろう。

コード

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

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    map<int, int> mp;
    rep(i, 0, N)
    {
        int A, C;
        cin >> A >> C;
        if (mp[C] == 0)
            mp[C] = A;
        else
            mp[C] = min(mp[C], A);
    }

    int ans = 0;
    for (auto &&m : mp)
        chmax(ans, m.second);

    cout << ans << endl;
}

atcoder.jp

実装時間: 10分