数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序：在游戏开始前查找孩子人数的最小值和最大值
假设我们有一个包含K个元素的数组A。考虑一个游戏中，有N个玩家和一个游戏管理员。这个游戏共有K轮。在第i轮中，游戏管理员宣布组成A[i]个孩子的群体。然后，剩余的孩子尽可能多地组成A[i]个孩子的群体。一个孩子不能参加多个群体。那些没有组群的孩子离开游戏。其他人继续下一轮。一轮可能没有玩家离开。最后，在第K轮之后，恰好剩下两个孩子，他们被宣布为获胜者。我们必须找到游戏开始前孩子人数的最小值和最大值，或者确定N的有效值不存在。
因此，如果输入类似A = [3, 4, 3, 2]，则输出将是[6, 8]，因为如果游戏以6个孩子开始，则它将继续
第一轮，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
更新于：2022年3月3日
浏览量：120
广告