โปรแกรม C++ หาจำนวนการดำเนินการน้อยที่สุดเพื่อฆ่าศัตรูด้วยมีด

โจทย์เกม: มีมีด n เล่ม แต่ละเล่มมีค่า {slash, throw} (ความเสียหายจากการระบาด และ โยน) โยนได้ครั้งเดียว ระบาดได้ไม่จำกัด ศัตรูมีชีวิต h หาจำนวนการดำเนินการ (ระบาด/โยน) น้อยที่สุดเพื่อลดชีวิตศัตรูเหลือ 0

ตัวอย่าง: n=2, h=11, knives={{4,5},{3,6}} ผลลัพธ์: 2 (โยนทั้งสองเล่ม: 5+6=11)

ขั้นตอนการแก้ปัญหา (Greedy)

1. หา val = max(slash_i) (ความเสียหายระบาดสูงสุด)
2. เรียงมีดตาม throw มากไปน้อย
3. โยนมีดที่ throw > val ทีละเล่ม ลบ h นับ res++ ถ้า h ≤ 0 คืน res
4. ถ้ายังไม่ตาย ใช้มีดระบาดที่ดีที่สุด (val) ซ้ำๆ: คืน res + ceil(h / val)

ตัวอย่างโค้ด C++

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

void solve(int n, int h, vector<pair<int,int>> knives) {
    int val = 0;
    for (int i = 0; i < n; i++) val = max(val, knives[i].first);
    sort(knives.begin(), knives.end(), [](auto &a, auto &b) {
        return a.second > b.second;
    });
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (knives[i].second > val) {
            h -= knives[i].second;
            res++;
            if (h <= 0) { cout << res << endl; return; }
        } else break;
    }
    cout << (res + (h + val - 1) / val) << endl;
}

int main() {
    int n = 2, h = 11;
    vector<pair<int,int>> knives = {{4,5},{3,6}};
    solve(n, h, knives);
    return 0;
}

อินพุต / เอาต์พุต

Input: 2, 11, {{4,5},{3,6}}

Output: 2