[ABC319F] Fighter Takahashi

CI_is_safe · 2023-09-12 18:59:45 · 题解

与其他题解截然不同的思路。

发现如果确定了吃药顺序，那么只要可以打一只怪兽一定打（因为先加后乘优于先乘后加），不可以打了，依次吃枚举顺序的药。复杂度 O(m!n\log n)。

可能会超时，所以我们考虑随机化其中几个排列，然后计算，若存在合法的方式，那么就 Yes，否则就 No。

注意到可以使用 C++ 的 chrono 头文件提供的方式或者 C 的 clock() 进行卡时（我卡到 1900ms），可能会 WA，多交几发就好。

代码（注意多交几次！）