C++ এ সর্বোত্তম অ্যাকাউন্ট ব্যালেন্সিং

ধরুন বন্ধুদের একটি দল ছুটিতে গিয়েছিল এবং কখনও কখনও তারা একে অপরকে টাকা ধার দেয়৷ তাই উদাহরণ হিসেবে, অমিত বিক্রমের মধ্যাহ্নভোজের জন্য $10 দিয়েছিলেন। পরে চন্দন অমিতকে ট্যাক্সি ভাড়ার জন্য ৫ ডলার দেয়। আমাদের এমন একটি মডেল ডিজাইন করতে হবে যেখানে প্রতিটি লেনদেন একটি টিপল (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 লাগবে,

• ret :=inf

• যখন (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]

• রিটার্ন (যদি ret একই হয় inf, তাহলে 0, অন্যথায় ret)

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• একটি মানচিত্র 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

• প্রতিটি কী-মানের জোড়ার জন্য i তে m, do −

  • যদি 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