12 人解决，23 人已尝试。
12 份提交通过，共有 32 份提交。
6.2 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
In a robust computer system, one of the most important pieces is the cooling. Without proper cooling, processors can heat up to over 400 degrees C. The reliability of a system can be measured by determining how many fans can fail without risking the system processor. Each fan can be assigned a value indicating how much capacity it has to cool the system, and we can define a minimum cooling capacity, which the sum of the fan capacities must exceed or equal to properly cool the system. We define a Failure Set as a set of fans which are not necessary to cool the system. In other words, if the fans in a Failure Set break, the system can still be properly cooled by the remaining fans. The count of a Failure Set is the number of fans in the set.
To measure the reliability, we will define two values, the Maximum Failure Set (MFS) and the Maximum Failure Count (MFC). A MFS is a Failure Set of fans with the largest count possible. A set of fans may have more than one MFS (see below). A Failure Set is an MFS if and only if there are no Failure Sets with a higher count. 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.
Consider the fan set with capacities 1, 2, 3, and a cooling requirement of 2. Two MFSs with a count of 2 exist: fans 1 and 3, or fans 1 and 2. However, the MFC is not 2 because fans 2 and 3 is not a Failure set (fan 1 could not cool the system properly by itself). Thus, the MFC is 1, because if any single fan fails, the system can still be cooled.
You will be given N capacities, which designates how many units of cooling each fan provides, and an int minCooling, which designates the minimum units of cooling required to cool the system.
There are several test cases,each test case begins with two integers N(1<=N<=50) and M(1<=M<=50000).The next line contains N integers,shows the capacities of the N fans(They are greater than 0 and will not exceed 1000).The sum of all capacities will be greater than or equal to minCooling.
Output two numbers,seperated by a space, where the first number should be the number of fans in the Maximum Failure Set (MFS), and the second number should be the Maximum Failure Count (MFC).
3 2 1 2 3 4 22 8 5 6 7 9 1000 676 11 223 413 823 122 547 187 28
2 1 0 0 7 2 Hint Case 1: Example from the problem statement. Case 2: No fans can fail in this system. Case 3: If you eliminate fans with 676, 11, 413, 122, 547, 187, and 28, you are left with 223 + 823 = 1046 units of cooling, which is sufficient, yielding an MFS size of 7. If you eliminate 676, 823, and 547, you are left with only 984 units of cooling. All combinations of 2 or less fans breaking leaves sufficient cooling, so the MFC is 2.
12 人解决，23 人已尝试。
12 份提交通过，共有 32 份提交。
6.2 EMB 奖励。
创建: 16 年，8 月前.
修改: 7 年，3 月前.
最后提交: 4 年前.
来源: N/A