【每日一题】- 2020-08-21

[azl397985856]

有三种难度的睡目难度分别为 Easy,Medium,Hard,现在你总共有 E十EM+M十MH 十 H 道题。

各个字符串的含义如下：

• E表示有E道题目难度为Easy.
• EM表示有〔M道题目难度可以为Easy或Medium.
• M表示有M道题目难度为Medium。
• MH表示有MH道越目难度可以为Medium或Hard,
• H表示有H道题目难度为Hard,

你要用这些题目出尽可能多的模拟赛，为了保证题目质，且含有一定的区分度，每场模拟赛要包含Easy，Medium，Hard三种难度的题目各一道。求你．多能出多少场模拟赛．

function t(E, EM, M, MH, H) {}

t(2, 2, 1, 2, 2)

[suukii]

思路

因为每场模拟赛都要包含 Easy，Medium，Hard 三种难度的题目各一道，能出多少场模拟赛就取决于这三者的短板，数量最少的题目决定了模拟赛的场次。

除了 E, M, H 三种难度确定的题目外，还有 EM 道可以是 E 或 M 的题目以及 MH 道可以是 M 或 H 的题目。我们可以用两层循环来枚举所有把 EM 分配给 E 和 M，以及把 MH 分配给 M 和 H 的情况。

复杂度

• 时间复杂度：$O(EM*MH)$。
• 空间复杂度：$O(1)$。

代码

JavaScript Code

function t(E, EM, M, MH, H) {
    let ans = 0;
    for (let i = 0; i <= EM; i++) {
        for (j = 0; j <= MH; j++) {
            ans = Math.max(ans, Math.min(E + i, M + (EM - i) + j, H + (MH - j)));
        }
    }
    return ans;
}

t(2, 2, 1, 2, 2); // 3

[azl397985856]

暴力

思路

代码（JS）

function t(E, EM, M, MH, H) {
 if (E < 1 && EM < 1) return 0
 if (EM < 1 && M < 1 && MH < 1) return 0
 if (H < 1) return 0
 return 1 + max(六种情况)
}

复杂度分析

• 时间复杂度：$O(6 ^ N)$，其中 N 为 min(E, EM, M, MH, H)
• 空间复杂度：$O(6 ^ N)$，其中 N 为 mim(E, EM, M, MH, H)

记忆化递归（略）

复杂度分析

• 时间复杂度：$O(E EM M MH H)$
• 空间复杂度：$O(E EM M MH H)$

动态规划（略）

复杂度分析

• 时间复杂度：$O(E EM M MH H)$
• 空间复杂度：$O(E EM M MH H)$

贪心

思路

我们可以将 EM 到题 分为 i 道 E 和 EM - i 道 M。同理 MH 也是一样的。 因此总的可能就是 EM * MH。 我们暴力枚举所有可能求最大即可。

代码

function t(E, EM, M, MH, H) {
    let ans = 0
    for (let i = 0; i <= EM; i++) {
        for (j = 0; j <= MH; j++) {
            ans = Math.max(ans, Math.min(E + i, M + EM - i + j, H + MH - j))
        }
    }
    return ans
}

复杂度分析

• 时间复杂度：$O(EM * MH)$
• 空间复杂度：$O(1)$

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.