โปรแกรม C++ หาลำดับการโหลดทองบนสเกลน้ำหนักไม่ระเบิด

สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบต่างกัน n ตัว และอีกจำนวนหนึ่งคือ x มีทองคำอยู่ n ชิ้น น้ำหนักทองคือ A[i] เราจะนำ n ชิ้นนี้มาใส่ในเครื่องชั่งน้ำหนักทีละชิ้น แต่เครื่องชั่งมีข้อบกพร่องที่ผิดปกติ:หากน้ำหนักรวมบนเครื่องชั่งเป็น x ตรงทั้งหมด เครื่องชั่งจะระเบิด เราต้องตรวจสอบว่าเราสามารถใส่ทอง n ทั้งหมดลงบนตาชั่งในลำดับใด โดยไม่ทำให้เครื่องชั่งระเบิดในระหว่างกระบวนการ ถ้าเราทำได้ จงหาคำสั่งนั้น หากทำไม่ได้ ให้ทำเครื่องหมายว่า "เป็นไปไม่ได้"

ดังนั้น ถ้าอินพุตเป็น A =[1, 2, 3, 4, 8]; x =6 จากนั้นผลลัพธ์จะเป็น [8, 1, 2, 3, 4] คำสั่งอื่นๆ ก็ใช้ได้เช่นกัน

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

s := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   s := s + A[i]
if s is same as x, then:
   return "IMPOSSIBLE"
s := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   s := s + A[i]
   if s is same as x, then:
      print A[i + 1], A[i]
      (increase i by 1)
      Ignore following part, skip to the next iteration
   print A[i]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

void solve(vector<int> A, int x) {
   int s = 0;
   int n = A.size();
   for (int i = 0; i < n; i++) {
      s += A[i];
   }
   if (s == x) {
      cout << "IMPOSSIBLE";
      return;
   }
   s = 0;
   for (int i = 0; i < n; i++) {
      s += A[i];
      if (s == x) {
         cout << A[i + 1] << ", " << A[i] << ", ";
         i++;
         continue;
      }
      cout << A[i] << ", ";
   }
}
int main() {
   vector<int> A = { 1, 2, 3, 4, 8 };
   int x = 6;
   solve(A, x);
}

อินพุต

{ 1, 2, 3, 4, 8 }, 6

ผลลัพธ์

1, 2, 4, 3, 8,