假设我们有一个包含 K 个元素的数组 A。考虑一下，在一场游戏中，有 N 个玩家，并且有一个游戏主持人。这个游戏有K轮。在第 i 轮游戏中，游戏主持人宣布将 A[i] 个孩子组成小组。然后剩下的孩子组成尽可能多的 A[i] 孩子组。一个孩子不能参加多个小组。没有组的人离开游戏。其他人进入下一轮。一轮可能没有玩家损失。最终，第K轮结束后，只剩下两个孩子，他们被宣布为获胜者。我们必须在开始之前找到游戏中可能存在的最小和最大的孩子数量，或者确定 N 不存在有效值。
因此，如果输入类似于 A = [3, 4 , 3, 2]，那么输出将是 [6, 8]，因为如果游戏以 6 个孩子开始，那么它会继续
在第 1 轮中，其中6人组成两组，每组3人
-
他们组成两组，分别有4个和2个孩子
立即学习“C++免费学习笔记（深入）”；
然后一组1 个孩子和 3 个孩子，1 个将离开游戏
他们三个组成 1 和 2 的一组。1 个将离开。
最后 2 个孩子被宣布为获胜者。
步骤
为了解决这个问题，我们将遵循以下步骤 -
n := size of A
Define a large array a, l, r, a of size: 100010.
l := 2, r = 2
for initialize i := 1, when i <= n, update (increase i by 1), do:
a[i] := A[i - 1]
for initialize i := n, when i >= 1, update (decrease i by 1), do:
x := a[i], L := (l + x - 1)
if L > R, then:
return -1, 0
l := L, r = R + x - 1
return l, r示例
让我们看看以下实现，以便更好地理解 -
#includeusing namespace std; void solve(vector A){ int n = A.size(); int l, r, a[100010]; l = 2, r = 2; for (int i = 1; i <= n; i++) a[i] = A[i - 1]; for (int i = n; i >= 1; i--){ int x = a[i], L = (l + x - 1) / x * x, R = r / x * x; if (L > R){ cout << "-1, 0"; } l = L, r = R + x - 1; } cout << l << ", " << r << endl; return; } int main(){ vector A = { 3, 4, 3, 2 }; solve(A); }
输入
{ 3, 4, 3, 2 }输出
6, 8
