SP32202 SHAREIT - Share It

在宿舍里住着一些朋友，他们每天共享许多物品。为了节省开销，他们总是尽量避免浪费任何金钱。当他们需要某些可以共享的物品时，总会一起购买。不过，难题来了：购买这些物品时，很难立即把价格平摊到每个人身上。例如，一件物品的价格为 10 元，3 个朋友共享，每人需支付 3.33 元，这样的分摊方式很难在当下完成。不是每个人的钱包里都恰好有 3.33 元来结算。假设他们总是使用现金，并且会平均分担物品的价格。 为了简化生活，他们想出了一种方法： 「每次购买的共享物品，不必立即分摊费用。由其中一人或几人先垫付，然后记下这笔交易，月底再进行结算。」 因此，他们需要一个软件，用来记录共享物品的购买信息，包括物品名称、购买日期、价格，谁在购买时支付了多少，以及这物品要在谁之间共享。到了月底，这个应用程序将能计算出谁欠谁多少钱。 说起来挺简单的，但实际操作还需要…… 1. 到月底，应用程序应帮助找出最少的对账交易数量。例如，A 需要支付给 B 10 元（A->B: 10），而 B 需要支付给 A 5 元（B->A: 5），实际上 A 只需要支付给 B 5 元（A->B: 5）即可，只需一笔交易。同理，如果 A->B: 10，B->C: 10，则可以让 A 直接支付给 C 10 元（A->C: 10），也只需一笔交易。 2. 所有最终结算的交易金额总和应最小化。例如，A->B: 10 和 B->C: 5（总金额 = 10 + 5 = 15），那么可以安排为 A->B: 5 和 A->C: 5（总金额 = 5 + 5 = 10），以便总金额更少。

- 第一行输入包含测试用例的数量 **T (1 ≤ T ≤ 100)**。接下来是 **T** 个测试用例。 - 每个测试用例的第一行包括两个整数 **N** 和 **S**，分别表示朋友的数量 **N (1 ≤ N ≤ 100)**（编号从 1 到 **N**）和一个月内交易的数量 **S (1 ≤ S ≤ 1000)**。 - 每个测试用例接下来的 **S** 行描述 **S** 笔交易，每笔交易如下（各值以空格分隔，尖括号仅用于说明）：` ... `，其中 - **F (1 ≤ F ≤ N)**：垫付款的朋友编号， - **A (0.01 ≤ A ≤ 10000.00)**：**F** 在此交易中支付的金额（保留两位小数）， - **B_i (0 或 1)**：若为 0，则金额 **A** 不与编号为 **i** 的朋友共享；若为 1，则共享金额。金额至少与一个朋友共享。（注意：如果金额 **A** 要在 **n** 位朋友之间共享，则每份金额即 **A/n** 截断到两位小数。例如，若 **A=10.00** 且 **n=3**，则 **A/n=3.33**；若 **A=20.00** 且 **n=3**，则 **A/n=6.66**）

对于每个测试用例，找到一种交易方案，使最后结算中的交易次数最小，且交易金额总和也是最小的（称为 **MINIMUM\_SUM\_AMOUNTS**）。 - 对于每个测试用例，输出一行，列出 **MINIMUM\_SUM\_AMOUNTS**，保留两位小数。 **本翻译由 AI 自动生成**