Atcoder Beginner Contest 184 F Programming Contest(暴力枚举+二分）_高桥将参加一个编程比赛,比赛持续t分钟,提出n个问题。凭着他的超感知觉,他已经知

作者：机器笔尖舞者 | 2024-02-01 08:33:07

踩

高桥将参加一个编程比赛,比赛持续t分钟,提出n个问题。凭着他的超感知觉,他已经知

题意：
高桥将参加编程竞赛，竞赛持续了T分钟，并提出了V问题。
凭借他的超感官知觉，他已经知道它将需要ai分钟解决第i个问题。
他将从N个问题中选择零个或多个要解决的问题，因此解决这些问题所花费的总时间不会超过T分钟。
找到他解决问题选择所需的最长时间。
1<=N<=40
1<=T<=10^9
1<=a[i]<=10^9
题解：
看到数据范围首先想到枚举2^N,发现肯定会超时。于是我们可以将N分成两半，然后分别枚举子集，得到两个集合。然后对两个集合的进行二分求出最大的所需时间。时间复杂度为 $2^{N/2}$ log $2^{N/2}$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/52650

Atcoder Beginner Contest 184 F Programming Contest(暴力枚举+二分）_高桥将参加一个编程比赛,比赛持续t分钟,提出n个问题。 凭着他的超感知觉,他已经知

Atcoder Beginner Contest 184 F Programming Contest(暴力枚举+二分）_高桥将参加一个编程比赛,比赛持续t分钟,提出n个问题。凭着他的超感知觉,他已经知