C++での最適なアカウントバランシング

友人のグループが休暇に出かけ、時にはお互いにお金を貸したとします。例として、アミットはビクラムの昼食代を10ドルで支払いました。その後、チャンダンはアミットにタクシー料金として5ドルを与えました。各トランザクションがタプル（x、y、z）として扱われるモデルを設計する必要があります。これは、人xが人yに$zを与えたことを意味します。

Amit、Bikram、およびChandanがそれぞれ人物0、1、および2であるとすると、トランザクションは[[0、1、10]、[2、0、5]]として表すことができます。人々のグループ間の取引のリストがある場合、債務を決済するために必要な取引の最小数を見つける必要があります。

したがって、入力が[[0,1,10]、[2,0,5]]の場合、人＃0が人＃1に$ 10を与えたため、出力は2になります。次に、人＃2が人＃0に$5を与えました。ここでは2つのトランザクションが必要です。借金を清算する1つの方法は、人＃1が人＃0と＃2にそれぞれ$5を支払うことです。

これを解決するには、次の手順に従います-

• 配列を定義するv

• 関数dfs（）を定義します。これにはidxが必要です

• ret：=inf

• （idx

  • （idxを1増やします）

• 初期化i：=idx + 1の場合、i −サイズがvの場合、更新（iを1増やします）、実行-

  • v [i] * v [idx] <0の場合、-

    • v [i]：=v [i] + v [idx]

    • ret：=retの最小値と1+ dfs（idx + 1）

    • v [i]：=v [i]-v [idx]

• return（retがinfと同じ場合は0、それ以外の場合はret）

• メインの方法から、次のようにします-

• 1つのマップを定義するm

• n：=tのサイズ

• 初期化i：=0の場合、i

  • u：=t [i、0]、v：=t [i、1]

  • bal：=t [i、2]

  • m [u]：=m [u] + bal

  • m [v]：=m [v] --bal

• mのキーと値のペアiごとに、次のようにします-

  • iの値の場合、-

    • vの最後にiの値を挿入します

  • （iを1増やします）

• dfs（0）の最小値とvのサイズを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector<int> v;
   int dfs(int idx) {
      int ret = INT_MAX;
      while (idx < v.size() && !v[idx])
         idx++;
      for (int i = idx + 1; i < v.size(); i++) {
         if (v[i] * v[idx] < 0) {
            v[i] += v[idx];
            ret = min(ret, 1 + dfs(idx + 1));
            v[i] -= v[idx];
         }
      }
      return ret == INT_MAX ? 0 : ret;
   }
   int minTransfers(vector<vector<int>>&t) {
      map<int, int> m;
      int n = t.size();
      for (int i = 0; i < n; i++) {
         int u = t[i][0];
         int v = t[i][1];
         int bal = t[i][2];
         m[u] += bal;
         m[v] -= bal;
      }
      map<int, int>::iterator i = m.begin();
      while (i != m.end()) {
         if (i->second)
            v.push_back(i->second);
         i++;
      }
      return min(dfs(0), (int)v.size());
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {{0,1,10},{2,0,5}};
   cout << (ob.minTransfers(v));
}

入力

{{0,1,10},{2,0,5}}

出力

2