Giả sử chúng ta có một mảng A với n phần tử và một số khác H. H là sức khỏe của kẻ thù. Chúng ta có n vũ khí và sức sát thương của vũ khí thứ i là A [i]. Các loại vũ khí khác nhau có thể được sử dụng để giết kẻ thù. Chúng ta không thể sử dụng cùng một loại vũ khí hai lần liên tiếp. Chúng ta phải đếm số lần tối thiểu chúng ta có thể sử dụng vũ khí để giết kẻ thù.
Vì vậy, nếu đầu vào là A =[2, 1, 7]; H =11, thì đầu ra sẽ là 3, bởi vì nếu chúng ta sử dụng vũ khí với sức sát thương 7, sau đó sử dụng 2 rồi lại sử dụng 7, chúng ta có thể giết kẻ thù.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
sort the array A n := size of A x := (A[n - 1] + A[n - 2]) return H / x * 2 + (H mod x + A[n - 1] - 1) / A[n-1]
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int H){
sort(A.begin(), A.end());
int n = A.size();
int x = (A[n - 1] + A[n - 2]);
return H / x * 2 + (H % x + A[n - 1] - 1) / A[n - 1];
}
int main(){
vector<int> A = { 2, 1, 7 };
int H = 11;
cout << solve(A, H) << endl;
} Đầu vào
{ 2, 1, 7 }, 11 Đầu ra
3