题目描述
一群朋友在度假期间会相互借钱。比如说，小爱同学支付了小新同学的午餐共计 10 美元。如果小明同学支付了小爱同学的出租车钱共计 5 美元。我们可以用一个三元组 (x, y, z) 表示一次交易，表示 x 借给 y 共计 z 美元。用 0, 1, 2 表示小爱同学、小新同学和小明同学（0, 1, 2 为人的标号），上述交易可以表示为 [[0, 1, 10], [2, 0, 5]]。
给定一群人之间的交易信息列表，计算能够还清所有债务的最小次数。
注意：
一次交易会以三元组 (x, y, z) 表示，并有 x ≠ y 且 z > 0。
人的标号可能不是按顺序的，例如标号可能为 0, 1, 2 也可能为 0, 2, 6。
示例 1：
输入：
2
0 1 10
2 0 5
输出：
2
解释：
人 #0 给人 #1 共计 10 美元。
人 #2 给人 #0 共计 5 美元。
需要两次交易。一种方式是人 #1 分别给人 #0 和人 #2 各 5 美元。
示例 2：
输入：
4
0 1 10
1 0 1
1 2 5
2 0 5
输出：
1
解释：
人 #0 给人 #1 共计 10 美元。Person #0 gave person #1 $10.
人 #1 给人 #0 共计 1 美元。Person #1 gave person #0 $1.
人 #1 给人 #2 共计 5 美元。Person #1 gave person #2 $5.
人 #2 给人 #0 共计 5 美元。Person #2 gave person #0 $5.
因此，人 #1 需要给人 #0 共计 4 美元，所有的债务即可还清。
package main
import "fmt"
func main() {
var n, x, y, z int
m := make(map[int]int)
fmt.Scan(&n)
for n > 0 {
fmt.Scan(&x, &y, &z)
m[x] += z
if m[x] == 0 {
delete(m, x)
}
m[y] -= z
if m[y] == 0 {
delete(m, y)
}
n--
}
fmt.Println(len(m) - 1)
}
第一行为三元组个数，之后每一行为一个三元组，三元组成员间以空格分隔
输出能够还清所有债务的最小次数
输入样例 1 复制
2 0 1 10 2 0 5
输出样例 1
2
分析：
刚开始所有人债务为0，然后每输入一行，更新2个人的总债务数，最后把总债务数为0的剔除，看还剩多少人。
代码：（40%用例通过）
分析：
我这里求出了一共有m个人的债务总数不为0，输出的是m-1
实际上应该进一步求出，这m个数，最多可以分为多少组，使得每一组的总和都为0，假设k组，输出m-k
对于有的用例k=1，但是有的用例k>1
如何求k，待完善。
package main
import "fmt"
func minTransfers(transactions [][]int) int {
balances := make(map[int]int)
for _, t := range transactions {
balances[t[0]] -= t[2]
balances[t[1]] += t[2]
}
debts := []int{}
for _, v := range balances {
if v != 0 {
debts = append(debts, v)
}
}
return settleDebts(debts, 0)
}
func settleDebts(debts []int, start int) int {
for start < len(debts) && debts[start] == 0 {
start++
}
if start == len(debts) {
return 0
}
minTrans := int(^uint(0) >> 1)
for i := start + 1; i < len(debts); i++ {
if debts[i]*debts[start] < 0 {
debts[i] += debts[start]
minTrans = min(minTrans, 1+settleDebts(debts, start+1))
debts[i] -= debts[start]
}
}
return minTrans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
transactions := [][]int{{0, 1, 10}, {2, 0, 5}}
fmt.Println(minTransfers(transactions))
}
package main
import "fmt"
var input [100]int
var result = int(^uint(0) >> 1)
/**
1.递归写法，每次递归返回后，需要清除上一步的操作；
2.for循环里面嵌套递归；
3.我的代码是预置了100人，人数这里还需要优化下。
*/
func main() {
var len int
fmt.Scan(&len)
for len > 0 {
var x, y, z int
fmt.Scan(&x, &y, &z)
input[y] += z
input[x] -= z
len--
}
res := dfs(0, 0)
fmt.Print(res)
}
func dfs(start, num int) int {
for start < 100 && input[start] == 0 {
start++
}
if start == 100 {
result = min(result, num)
}
for i := start + 1; i < 100; i++ {
if (input[i] < 0 && input[start] > 0) || (input[i] > 0 && input[start] < 0) {
input[i] += input[start]
result = min(result, dfs(start+1, num+1))
input[i] -= input[start]
}
}
return result
}
func min(a, b int) int {
if a < b {
return a
}
return b
}