けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 112 B - Time Limit Exceeded (7Q, 灰色, 100 点)

「線形探索」と「最小値を求める」の組み合わせ技!

問題概要

 N 個のペア値  (c_{1}, t_{1}), \dots, (c_{N}, t_{N}) が与えられる。

 t_{i} \le T を満たすような  i についての、 c_{i} の最小値を求めよ。そのような  i が存在しない場合は "TLE" と出力せよ。

解法

for 文を用いて、各 i について t[i] <= T かどうかを判定し、そのような i に対して res = min(res, c[i]) などと処理すれば OK。

コード

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

int main() {
    int N, T;
    cin >> N >> T;
    
    const int INF = 1 << 29;
    int res = INF;  // c[i] <= 1000 なので、それより大きい数で初期化
    for (int i = 0; i < N; ++i) {
        int c, t;
        cin >> c >> t;
        
        // T 以内についてのみ、res と c を比べる
        if (t <= T) {
            res = min(res, c);
        }
    }
    
    if (res < INF) cout << res << endl;
    else cout << "TLE" << endl;
}