Katana Thrower [AtCoder Beginner Contest 085 D]

https://abc085.contest.atcoder.jp/tasks/abc085_d

解法

https://abc085.contest.atcoder.jp/submissions/1952643

貪欲に解けないか考えてみよう。
まず刀を振る場合を考えると一番強い刀を振るだけでいい。
そのため、Aの最大値maを求めておこう。
つぎに、刀を投げる場合を考えると、ma以下の刀は投げる必要はない。
かつ、maより大きい刀はなるべく投げたほうがいい。
その為、どんどん投げていき、余ったら残りは一番強い刀を振って倒すのが最適。
これをやって求めていこう。
投げる動作はO(N)なので大丈夫だが、残りは1回1回振るとTLEする可能性があるので切り上げで求めよう。
最初に投げてあとで振ると、投げた刀にAがmaの刀が含まれるかもしれないと考えるかもしれないが、その場合は先に振っておいて全部投げたと考えれば問題ない。

int N, H, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
int solve() {
    int ma = 0;
    rep(i, 0, N) ma = max(ma, A[i]);
    vector<int> v;
    rep(i, 0, N) if (ma < B[i]) v.push_back(B[i]);
    sort(v.begin(), v.end(), greater<int>());
 
    int ans = 0;
    fore(x, v) {
        ans++;
        H -= x;
        if (H <= 0) return ans;
    }
 
    ans += (H + ma - 1) / ma;
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> H;
    rep(i, 0, N) cin >> A[i] >> B[i];
    cout << solve() << endl;
}