1027. 最优账单平衡（待完善）-dfs

题目描述

一群朋友在度假期间会相互借钱。比如说，小爱同学支付了小新同学的午餐共计 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
}