SP7934 OSPROB1 - Operating System Problems (Task Scheduling)

众所周知，操作系统（OS）是一种控制计算机程序执行的软件，并可能提供各种服务。现代操作系统虽然使用起来很方便，也提供了许多服务，但它们的设计并不简单。设计一个优秀的操作系统需要大量的工作和时间。但即便如此，没有一个操作系统是完美的，要么不够好用，要么不够安全（比如存在很多病毒）。Lingates 是一名追求完美的杰出程序员，为了实现理想，他决定不使用现有的操作系统，而是自己编写一个。可他发现，自己一个人完成这项工作非常困难，因此需要你的帮助。 作为一名有尊严的程序员，Lingates 不会在每一回合中让你分担相等或更多的工作（即每一回合 Lingates 的工作量必须多于你的）。在每一回合中，你和 Lingates 需要分配不同的工作。这些工作是相关联的，所以最好选择相邻的工作来进行分配。举个例子，如果有 **5** 项工作 **5, 2, 7, 1, 3**，那么 Lingates 可以选择第 1 项工作（5），并将第 2 项工作（2）给你。但你不能选择第 2 和第 3 项工作，因为它们的总和是 **7+2=9**，超过了 Lingates 的工作量（**5**）。而且，你也不能选择第 2 和第 4 项工作，因为它们不是连续的。当你们完成各自的工作后，会再次分配新的任务。每一回合你们可以承担任意多的工作数量。例如，Lingates 可以在第一回合完成第 1 和第 2 项工作，并且不给你安排任何任务；或者他可以选择完成第 1、2、3 项工作（总共 **5+2+7=14**），并给你第 4 项（**1**）或者两个项目（**1+3=4**）。由于你在协助他，因此工作分配由你决定，但需要确保每次 Lingates 的工作量都比你的多。作为品格高尚的程序员，你自然希望进行合理的分配，以最大化你的总工作量。 请编写一个程序来找出最优的工作分配方案。输入给定的工作列表，输出下在这种最优分配下，Lingates 和你各自的总工作量。Lingates 会接受你的分配，只要在每一回合中你的工作量都小于他的即可。

第一行为一个整数 $T$，表示测试用例的数量（$T \leq 500$）。每个测试用例的第一行是一个整数 $n$ ($0 \leq n \leq 100$)，表示工作项的数量。接下来的一行包含 $n$ 个非负整数，表示每项工作的工作量（均小于 1000）。

对于每个测试用例，输出一行，显示两个整数，分别表示 Lingates 的总工作量和你的总工作量。 ## 示例 **输入：** ``` 4 3 1 2 3 5 5 2 7 1 3 5 6 6 6 6 6 7 4 9 5 7 6 5 1 ``` **输出：** ``` 6 0 12 6 18 12 20 17 ``` **解释：** - 在第一个例子中，你必须把所有三项工作都给 Lingates，因为 $1 < (2+3)$ 且 $(1+2) = 3$，所以你不能做任何工作。 - 第二个例子中，你可以给 Lingates 第一项工作（5），然后你自己拿第二项工作（2）。接着你可以给 Lingates 第三项工作（7），然后你自己拿剩下的工作（1+3）。 - 第三个例子中，你可以给 Lingates 前三项工作（6+6+6=18），然后你自己拿剩下的两项工作（6+6=12）。 - 在第四个例子中，你可以给 Lingates 工作 4 和 9，然后你自己拿 5 和 7。下一回合中，你可以给 Lingates 6，你自己拿 5。最后你可以给 Lingates 1。最终总工作量分别为（4+9+6+1）=20 和（5+7+5）=17。 **本翻译由 AI 自动生成**