โปรแกรม C++ ค้นหาเด็กจำนวนน้อยที่สุดและมากที่สุดในเกมก่อนเริ่ม

สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ K จำนวน พิจารณาว่าในเกมมีผู้เล่น N คนและมีปรมาจารย์เกมอยู่ที่นั่น เกมนี้มีรอบ K ในเกมรอบนั้นมาสเตอร์ประกาศจัดตั้งกลุ่มที่มีจำนวนลูก A[i] จากนั้นเด็กที่เหลือก็จะรวมกลุ่มของเด็ก A[i] ให้ได้มากที่สุด เด็กคนหนึ่งไม่สามารถเข้าร่วมหลายกลุ่มได้ ผู้ที่ถูกทิ้งไว้โดยไม่มีกลุ่มออกจากเกม คนอื่นๆ เข้าสู่รอบต่อไป รอบอาจมีผู้เล่นไม่มีการสูญเสีย ในท้ายที่สุด หลังจากรอบ K-th เหลือลูกสองคนพอดี และประกาศให้เป็นผู้ชนะ เราต้องหาจำนวนเด็กที่เล็กที่สุดและมากที่สุดเท่าที่จะเป็นไปได้ในเกมก่อนเริ่ม หรือพิจารณาว่าไม่มีค่า N ที่ถูกต้อง

ดังนั้นหากอินพุตเป็น A =[3, 4, 3, 2] เอาต์พุตจะเป็น [6, 8] เพราะหากเกมเริ่มต้นด้วย 6 ลูก ก็จะดำเนินต่อ

• ในรอบที่ 1 มี 6 คน 2 กลุ่ม กลุ่มละ 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