친구 그룹이 휴가를 갔다가 때때로 서로에게 돈을 빌려주었다고 가정해 보겠습니다. 예를 들어 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]]와 같으면 0번 사람이 1번 사람에게 $10를 주었으므로 출력은 2가 됩니다. 그런 다음 사람 #2는 사람 #0에게 $5를 주었습니다. 여기서 두 가지 트랜잭션이 필요합니다. 부채를 청산하는 한 가지 방법은 1번 사람이 0번 사람과 2번 사람에게 각각 5달러를 지불하는 것입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
배열 정의 v
-
dfs() 함수를 정의하면 idx가 필요합니다.
-
ret :=inf
-
동안 (idx
-
(idx를 1씩 증가)
-
-
initialize 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)
-
주요 방법에서 다음을 수행하십시오 -
-
하나의 맵 정의
-
n :=t의 크기
-
initialize i :=0의 경우, i
-
유 :=t[i, 0], v :=t[i, 1]
-
발 :=t[i, 2]
-
m[u] :=m[u] + 발
-
m[v] :=m[v] - 발
-
-
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