Run Code
|
API
|
Code Wall
|
Users
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Splitwise Problem - 1
#include <bits/stdc++.h> using namespace std; const int N = 1e6; int balance[N]; int main() { int i, n, m, u, v, w; cin >> n >> m; for(i=0; i<m; i++) { cin >> u >> v >> w; //u has to pay v an amount w balance[u] -= w; balance[v] += w; } multiset<int> S; for(i=0; i<n; i++) if(balance[i] != 0) S.insert(balance[i]); int count = 0; while(!S.empty()) { int poor = *S.begin(); S.erase(S.begin()); int rich = *S.rbegin(); S.erase(prev(S.end())); int amount = min(-poor, rich); count++; //poor pays amount "amount" to rich poor += amount; rich -= amount; if (poor) S.insert(poor); if (rich) S.insert(rich); } cout << count << endl; }
run
|
edit
|
history
|
help
0
Please
log in
to post a comment.
homework
NonparaSign
container access all elements
Date n Time Macros
Find the Duplicate Number in array of n+1 integers having elements from 1 to n
Graph Theory 2
Test 19(2020)
1234
articulation points and bridges
w1
Please log in to post a comment.