Tối thiểu số lượt đánh để tiêu diệt kẻ thù với vũ khí không dùng liên tiếp bằng C++

Mô tả bài toán

Mảng A sức mạnh n vũ khí. Kẻ thù máu H. Không dùng cùng vũ khí 2 lượt liên tiếp. Tìm số lượt đánh tối thiểu để H ≤ 0.

Ví dụ

A=[2,1,7], H=11 → Dùng 7,2,7 → 3 lượt.

Thuật toán

Sắp xếp A. Hai vũ khí mạnh nhất: x=A[n-1], y=A[n-2]. Mỗi cặp (x+y) gây sát thương x+y. Số cặp full = H/(x+y). Dư = H%(x+y). Nếu dư==0 → 2*full. Nếu dư ≤ x → 2*full+1. Else → 2*full+2. Công thức gọn: H/(x+y)*2 + (H%(x+y)+x-1)/x.

Code C++

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

int solve(vector A, int H) {
    sort(A.begin(), A.end());
    int n = A.size();
    int x = A[n-1], y = A[n-2];
    int pairDmg = x + y;
    return H / pairDmg * 2 + (H % pairDmg + x - 1) / x;
}

int main() {
    vector A = {2,1,7};
    int H = 11;
    cout << solve(A, H) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: {2,1,7}, 11

Output: 3