C++ 中游戏中最后一个怪物的最小最终生命值

问题陈述

给定 N 个怪物，每个怪物都有初始生命值 h[i]，它是一个整数。如果怪物的生命值大于 0，则该怪物还活着。

在每一轮中，一个随机怪物会杀死另一个随机怪物，被攻击的怪物的生命值会减少攻击怪物的生命值的数量。这个过程会持续到只剩下一个怪物为止。最后一个剩下的怪物的最小可能生命值是多少。

示例

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

算法

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

H(min) = 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

Narendra Kumar

更新于: 2019-11-22

346 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始