Chương trình C++ tìm số phép ít nhất tiêu diệt kẻ thù bằng dao ném/cắt

Mô tả bài toán

Có n con dao, dao i gây sát thương slash_i (cắt, không giới hạn lần) và throw_i (ném, 1 lần). Kẻ thù máu h. Tìm số phép (cắt/ném) ít nhất để hạ máu ≤ 0.

Ví dụ

n=2,h=11, knives={{4,5},{3,6}}. Đầu ra: 2 (ném cả 2: 5+6=11).

Thuật toán (Tham lam)

1. Tìm maxSlash = max(slash_i).
2. Sắp xếp dao theo throw giảm dần.
3. Duyệt dao: nếu throw_i > maxSlash thì ném (giảm h, tăng đếm). Dừng khi hoặc throw_i ≤ maxSlash.
4. Nếu 0, dùng dao cắt tốt nhất: thêm ceil(h/maxSlash) phép cắt.

Đoạn mã C++

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

void solve(int n,int h,vector<pair<int,int>> knives){
    int maxSlash=0;
    for(auto &k:knives) maxSlash=max(maxSlash,k.first);
    sort(knives.begin(),knives.end(),
         [](auto &a,auto &b){return a.second>b.second;});
    int res=0;
    for(auto &k:knives){
        if(k.second>maxSlash){
            h-=k.second; res++;
            if(h<=0){ cout<