Tuyên bố vấn đề
Cho N quái vật, mỗi quái vật có sức khỏe ban đầu h [i] là một số nguyên. Một con quái vật còn sống nếu lượng máu của nó lớn hơn 0.
Trong mỗi lượt, một quái vật ngẫu nhiên giết một quái vật ngẫu nhiên khác, quái vật bị tấn công, lượng máu của nó giảm theo lượng máu của quái vật tấn công. Quá trình này được tiếp tục cho đến khi còn lại một con quái vật duy nhất. Máu tối thiểu có thể có của con quái vật cuối cùng còn lại là bao nhiêu.
Ví dụ
Nếu mảng đầu vào là {2, 14, 28, 56} thì đầu ra sẽ là 2 vì Khi chỉ con quái vật đầu tiên tiếp tục tấn công 3 con quái vật còn lại, máu cuối cùng của con quái vật cuối cùng sẽ là 2, con số này tối thiểu.
Thuật toán
Chúng tôi có thể có câu trả lời cuối cùng bằng cách sử dụng công thức GCD dưới đây -
H (phút) =gcd (h1, h2,…, hn)
Ví dụ
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
int getPossibleHealth(int* health, int n) {
int currentGcd = gcd(health[0], health[1]);
for (int i = 2; i < n; ++i) {
currentGcd = gcd(currentGcd, health[i]);
}
return currentGcd;
}
int main() {
int health[] = { 4, 6, 8, 12 };
int n = sizeof(health) / sizeof(health[0]);
cout << "Possible final health = " << getPossibleHealth(health, n) << endl;
return 0;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Possible final health = 2