ABC085: D - Katana Thrower
問題
解説
の最大値以下のを持つ刀は使う必要がない。の最大値より大きいを持つ刀をすべて投げ、最大値を持つ刀を振って残り回数分だけ攻撃すれば良い。最初に振って攻撃したと思えば、振った刀を投げたとしても矛盾はない。
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"; }