C++-Programm zum Ermitteln der minimalen und maximalen Anzahl von Kindern vor Spielbeginn

假设我们有一个包含 K 个元素的数组 A。考虑一下，在一场游戏中，有 N 个玩家，并且有一个游戏主持人。这个游戏有K轮。在第 i 轮游戏中，游戏主持人宣布将 A[i] 个孩子组成小组。然后剩下的孩子组成尽可能多的 A[i] 孩子组。一个孩子不能参加多个小组。没有组的人离开游戏。其他人进入下一轮。一轮可能没有玩家损失。最终，第K轮结束后，只剩下两个孩子，他们被宣布为获胜者。我们必须在开始之前找到游戏中可能存在的最小和最大的孩子数量，或者确定 N 不存在有效值。

因此，如果输入类似于 A = [3, 4 , 3, 2]，那么输出将是 [6, 8]，因为如果游戏以 6 个孩子开始，那么它会继续

• 在第 1 轮中，其中6人组成两组，每组3人

• 他们组成两组，分别有4个和2个孩子

• 然后一组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

示例

让我们看看以下实现，以便更好地理解 -

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> 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<int> A = { 3, 4, 3, 2 };
   solve(A);
}

输入

{ 3, 4, 3, 2 }

输出

6, 8

Das obige ist der detaillierte Inhalt vonC++-Programm zum Ermitteln der minimalen und maximalen Anzahl von Kindern vor Spielbeginn. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!