資料結構
網路
關係資料庫管理系統 (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
廣告