C++ 程序在不爆炸的情况下找到将金块加载到体重秤上的顺序

假设我们有一个包含 n 个不同元素的数组 A，以及另一个数字 x。有 n 块金块。第 i 块金块的重量为 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,

Arnab Chakraborty

更新于： 03-Mar-2022

103 次浏览

开启您的 事业

完成课程以获得认证

开始