C ++中游戏中最后一个怪物的最小可能最终健康状况

问题陈述

给定N个怪兽，每个怪兽的初始生命值h [i]为整数。如果怪物的生命值大于0，则它仍然存在。

在每一回合中，随机怪物杀死另一个随机怪物，即被攻击的怪物，其生命值会受到攻击怪物的生命值的影响而降低。这个过程一直持续到剩下一个怪物为止。最后剩下的怪物的最小可能生命值是多少。

示例

如果输入数组为{2，14，28，56}，则输出将为2，因为当仅第一个怪物继续攻击其余3个怪物时，最后一个怪物的最终生命值为2，这是最小值。

算法

我们可以使用下面的GCD公式获得最终答案-

H（最小值）= gcd（h1，h2，…，hn）

示例

#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;
}

输出结果

当您编译并执行上述程序时。它产生以下输出-

Possible final health = 2