게임이 시작되기 전 최소 및 최대 어린이 수를 찾는 C++ 프로그램-C++-php.cn

게임이 시작되기 전 최소 및 최대 어린이 수를 찾는 C++ 프로그램

WBOY

풀어 주다： 2023-08-27 15:21:02

앞으로

1239명이 탐색했습니다.

C++ 程序以找到游戏开始前的最小和最大儿童数量

K개의 요소를 포함하는 배열 A가 있다고 가정합니다. N명의 플레이어와 게임 마스터가 있는 게임을 생각해 보세요. 이 게임에는 K개의 라운드가 있습니다. 게임의 i 라운드에서 게임 마스터는 A[i] 어린이가 그룹으로 구성될 것이라고 발표합니다. 나머지 아이들은 가능한 한 많은 A[i] 아이들 그룹을 형성합니다. 어린이는 두 개 이상의 그룹에 참여할 수 없습니다. 그룹의 누구도 게임을 떠나지 않습니다. 다른 사람들은 다음 라운드로 진출합니다. 라운드에서 플레이어 손실이 없을 수 있습니다. 마침내 K 라운드가 끝난 후 두 명의 어린이만이 승자로 선언되었습니다. 시작하기 전에 게임에 존재할 수 있는 최소 및 최대 어린이 수를 찾거나 N에 유효한 값이 없는지 확인해야 합니다.

따라서 입력이 A = [3, 4, 3, 2]와 같으면 출력은 [6, 8]이 됩니다. 왜냐하면 게임이 6명의 어린이로 시작하면 1번째에서

계속되기 때문입니다. 둥글게, 6명이 3명씩 2개의 그룹을 구성합니다
각각 4명과 2명의 두 그룹을 구성합니다
그런 다음 1명의 어린이와 3명의 그룹, 1명은 게임을 떠납니다
3명은 그들은 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

로그인 후 복사

Example

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. -

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

로그인 후 복사