首页 > Minimax Tree
开通博客写题解
头像 Kur1su
发表于 2020-12-04 11:42:11
Description 给出一棵树，除了叶子节点外要给其他节点打上 k 个 min 和 n - l - k 个 max 的 tag ，要求根节点的 max状态下最大可能值, min状态下最小可能值。 Solution 在所有节点必须放满的情况下，要么是叶子，要么是max/min在贪心的条件下，如果只 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 BNDSBilly
发表于 2020-12-14 16:03:47
因为最大值和最小值求法对称，以求最小值为例。 要让尽量小的上来，可以贪心选择一条路前面都是min不够了后面就用max。因为如果min上面有max，max换到下面不会更差。 但是这条前面都是min的路选哪一条呢？显然是最后一个min节点的子节点里max取最小的。共k个min，所以取第k+1层所有节点的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”