ABC085: D - Katana Thrower

問題

D - Katana Thrower

解説

aの最大値以下のb_iを持つ刀iは使う必要がない。aの最大値より大きいb_iを持つ刀をすべて投げ、最大値を持つ刀を振って残り回数分だけ攻撃すれば良い。最初に振って攻撃したと思えば、振った刀を投げたとしても矛盾はない。

int main() {
    int N, H; cin >> N >> H;
    vector<int> a, b;
    for (int i = 0; i < N; i++) {
        int a_, b_; cin >> a_ >> b_;
        a.push_back(a_);
        b.push_back(b_);
    }
    auto max_a = *max_element(a.begin(), a.end());
    sort(b.rbegin(), b.rend());
    int count = 0;
    for (auto e: b) {
        if (e <= max_a || H <= 0) break;
        H -= e;
        count++;
    }
    if (H > 0) {
        count += (H + max_a - 1) / max_a;
    }
    cout << count << "\n";
}