सी++ में इष्टतम खाता संतुलन

मान लीजिए कि दोस्तों का एक समूह छुट्टी पर गया था और कभी-कभी वे एक-दूसरे को पैसे उधार देते थे। उदाहरण के तौर पर, अमित ने बिक्रम के लंच के लिए $10 का भुगतान किया। फिर बाद में चंदन ने अमित को टैक्सी के किराए के लिए 5 डॉलर दिए। हमें एक मॉडल डिजाइन करना होगा जहां प्रत्येक लेनदेन को टपल (x, y, z) के रूप में लिया जाता है, जिसका अर्थ है कि व्यक्ति x ने व्यक्ति को y $z दिया है।

मान लें कि अमित, बिक्रम और चंदन क्रमशः व्यक्ति 0, 1 और 2 हैं, लेन-देन को [[0, 1, 10], [2, 0, 5]] के रूप में दर्शाया जा सकता है। यदि हमारे पास लोगों के समूह के बीच लेन-देन की एक सूची है, तो हमें ऋण को निपटाने के लिए आवश्यक न्यूनतम लेनदेन की संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट [[0,1,10], [2,0,5]] जैसा है, तो आउटपुट 2 होगा, क्योंकि व्यक्ति #0 ने व्यक्ति को #1 $10 दिया है। फिर व्यक्ति #2 ने व्यक्ति को #0 $5 दिया। यहां दो लेनदेन की जरूरत है। कर्ज को निपटाने का एक तरीका है व्यक्ति #1 भुगतान करने वाले व्यक्ति #0 और #2 $5 प्रत्येक।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• सरणी को परिभाषित करें v

• फ़ंक्शन dfs() को परिभाषित करें, यह idx लेगा,

• रिट :=inf

• जबकि (idx

  • (आईडीएक्स को 1 से बढ़ाएं)

• इनिशियलाइज़ करने के लिए i :=idx + 1, जब i − v का आकार, अपडेट (i 1 से बढ़ाएँ), करें −

  • अगर v[i] * v[idx] <0, तो -

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

    • ret :=न्यूनतम रिट और 1 + dfs(idx + 1)

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

• वापसी (यदि रिट inf के समान है, तो 0, अन्यथा रिट)

• मुख्य विधि से निम्न कार्य करें -

• एक नक्शा परिभाषित करें मी

• n :=t का आकार

• इनिशियलाइज़ i :=0 के लिए, जब i

  • यू:=टी[i, 0], वी:=टी[i, 1]

  • बाल:=टी[i, 2]

  • एम[यू] :=एम[यू] + बाल

  • एम[वी] :=एम[वी] - बाल

• m में प्रत्येक कुंजी-मान युग्म i के लिए, −

  . करें

  • यदि i का मान है, तो -

    • v के अंत में 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