ความสมดุลของบัญชีที่เหมาะสมที่สุดใน C++

สมมุติว่ากลุ่มเพื่อนไปเที่ยวพักผ่อนและบางครั้งพวกเขาก็ให้เงินกัน ตัวอย่างเช่น Amit จ่ายค่าอาหารกลางวันของ Bikram ในราคา $10 ต่อมา Chandan ให้ Amit $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]] ผลลัพธ์จะเป็น 2 เนื่องจากบุคคลที่ #0 ให้บุคคลที่ #1 $10 จากนั้นคนที่ #2 ให้คนที่ #0 $5 จำเป็นต้องมีธุรกรรมสองรายการ วิธีหนึ่งในการชำระหนี้คือคนที่ #1 จ่ายให้คนที่ #0 และ #2 $5 ต่อคน

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

• กำหนดอาร์เรย์ v

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้ idx

• ret :=inf

• ในขณะที่ (idx <ขนาดของ v และไม่ใช่ v[idx] ไม่ใช่ศูนย์) ทำ -

  • (เพิ่ม idx ขึ้น 1)

• สำหรับการเริ่มต้น i :=idx + 1 เมื่อฉัน − ขนาดของ 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)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดหนึ่งแผนที่ m

• n :=ขนาดของเสื้อ

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • u :=t[i, 0], v :=t[i, 1]

  • bal :=t[i, 2]

  • m[u] :=m[u] + บาล

  • m[v] :=m[v] - บาล

• สำหรับแต่ละคู่คีย์-ค่า i ในหน่วย 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