Quiz
https://atcoder.jp/contests/abc085/tasks/abc085_d
Submit
https://atcoder.jp/contests/abc085/submissions/3878954
解き方
- 最後の一発は投げるでも切るでもいい。1番ダメージの大きいものでとどめを刺す
- 以下同様に、最後に投げた刀以外で最大ダメージの方法を探して選択する
- 強い投げを使い果たし、投げ攻撃力<切り攻撃力になった時は、あとはその刀で切るだけ
- 攻撃順番は左から行う。切切切投投投
追記:2020/10/19
- 上記はsort解法ですが、今なら「逆順に考える」&「pair<int, int>をpriority_queueに入れて強い攻撃から取り出す」とします
- AC https://atcoder.jp/contests/abc085/submissions/17517521
int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N,H; cin>>N>>H; priority_queue<PII> que; // (attack, attackable_num) rep(i,N){ ll a,b;cin>>a>>b; que.push({a,inf}); que.push({b,1}); } ll cnt=0; while(!que.empty()){ auto pa = que.top(); que.pop(); ll attack = pa.first; if(pa.second==inf){ // それで最後まで切り続ける ll num = (H+attack-1)/attack; p(cnt+num); return 0; }else{ // 投げ切り H -= attack; cnt++; if(H<=0){ p(cnt); return 0; } } } return 0; }