-1

我实际上正在练习贪婪算法，并且 topcoder 有问题..所以需要一些帮助....

问题是关于健壮的计算机系统.. http://www.topcoder.com/stat?c=problem_statement&pm=2235&rd=5070

我不明白什么是MFC。（最大失败次数）？

如果有人可以通过简单的示例阐明 MFC 的解释，那将是有帮助的！

谢谢..

如果您没有帐户，并且无法访问链接，那么问题如下：

在强大的计算机系统中，最重要的部分之一是冷却。如果没有适当的冷却，处理器的温度可能会高达 400 摄氏度以上。系统的可靠性可以通过确定有多少风扇可以在不危及系统处理器的情况下发生故障来衡量。可以为每个风扇分配一个值，指示它有多少容量来冷却系统，我们可以定义最小冷却能力，风扇容量的总和必须超过该值才能正确冷却系统。我们将故障集定义为一组不需要冷却系统的风扇。换句话说，如果故障集中的风扇发生故障，系统仍然可以由剩余的风扇适当冷却。故障集的计数是该集中的风扇数。

为了衡量可靠性，我们将定义两个值，最大故障集 (MFS) 和最大故障计数 (MFC)。MFS 是具有最大可能数量的风扇故障集。一组风扇可能有多个 MFS（见下文）。当且仅当不存在具有更高计数的故障集时，故障集才是 MFS。MFC 是最大值，因此所有计数 <= MFC 的风扇集都是故障集。换言之，任何 MFC 或以下尺寸的风扇都可能发生故障，系统仍将由剩余的风扇适当冷却。

考虑具有容量 1、2、3 和冷却要求 2 的风扇组。存在两个计数为 2 的 MFS：风扇 1 和 3，或风扇 1 和 2。但是，MFC 不是 2，因为风扇 2 和3 不是故障集（风扇 1 无法自行正确冷却系统）。因此，MFC 为 1，因为如果任何一个风扇发生故障，系统仍然可以冷却。

您将获得一个 int[] 容量，它指定每个风扇提供多少冷却单位，以及一个 int minCooling，它指定冷却系统所需的最小冷却单位。您的方法应该返回一个 int[]，其中第一个值应该是最大故障集 (MFS) 中的风扇数，第二个值应该是最大故障计数 (MFC)。

4

2 回答 2

1

我们将故障集定义为一组不需要冷却系统的风扇。换句话说，如果故障集中的风扇发生故障，系统仍然可以由剩余的风扇适当冷却。故障集的计数是该集中的风扇数。

当且仅当不存在具有更高计数的故障集时，故障集才是 MFS。

这一切都在问题陈述中。什么不清楚？

于 2011-07-13T06:18:51.980 回答
0

就像在问题陈述中一样：

The MFC is the largest value such that all fan sets with count <= MFC are Failure Sets. In other words, any set of fans of size MFC or less can fail, and the system will still be properly cooled by the remaining fans.

MFC的意思是如果我们任意选择n<=MFC风扇失效，那么系统仍然可以提供必要的散热需求。但是，至少存在一种情况，如果我们选择 MFC + 1 风扇发生故障，系统将无法提供所需的冷却要求。

祝 TopCoder 好运，学习愉快！

剧透：

只需找到其容量总和大于（总容量 - 冷却要求）的最小风扇数量 M。这些粉丝必须是最大的粉丝，因此是贪心算法部分。M - 1 就是答案。

于 2011-07-13T06:19:05.843 回答