大家好，今天周末算法专题选的问题是codeforces contest1400中的B题，RPG Protagonist，翻译过来就是RPG游戏当中主人公。看起来这个标题就很唬人，其实这也是codeforces的题目风格。
这道题的链接是：https://codeforces.com/contest/1400/problem/B
按照道理来说div2比赛当中的B题都不难，大概和LeetCode当中的Easy差不多，有时候要简单一些，有时候要难一些。一般来说属于大部分人都能做出来的题。但今天选的这道题有一点意外，它的通过人数比同一场的C题还要少。其实并不是它难，而是这题当中藏着一个思维陷阱，我觉得挺有意思的，所以今天的文章选了它。
codeforces和LeetCode题目很大的不同点在于codeforces当中的许多题目会有一个短的背景故事，而不是很枯燥地直接告诉你这道题是怎样怎样的你去算去吧。所以相比之下会有意思一些，当然在比赛的时候这也很考验选手的读题（英语）水平，你能不能过滤掉这些背景故事的干扰，迅速提炼出题干。
这题的背景故事是说你是一个RPG游戏当中的主人公，你和一个随从一起去铁匠铺买装备。你的目的是买尽可能多的斧子和剑，然后把这些武器融了获得铁锭。你和随从各有一个背包，你背包的容量是p，随从背包的容量是f。其中一把剑占的体积是s，一把战斧(war axe)占的体积是w。铁匠铺里一共有cnts把剑，cntw把斧子。
然后题目规定一把剑和一把斧子融了都可以获得一个铁锭，请问你最多可以获得多少铁锭？
其中1 <= p,f,s,w <= 1e9，1 <= cnts, cntw <= 2e5。
样例首先输入t，表示测试数据的组数。(1 <=t <= 1e4)
接着输入p和f，第二行输入cnts和cntw，最后一行输入s和w。
这题有意思的地方是看着挺像是个裸的背包问题，但是我们看看数据范围就知道不可能用背包问题来解。并且只有两种商品，其实也没有什么背包的必要。仔细分析一下会发现不管买剑还是买斧子，得到的收益是一样的，都是1。所以很自然地会往贪心算法上来想。
贪心法推演这道题的贪心策略很明显也很简单，既然只有两种商品，并且两种商品的收益一样，那么当然优先拿体积小的那个商品了。但很明显这样可能会造成体积的浪费，我们假设s的体积小于w，我们优先拿s。当我们拿完了s之后，发现剩下的体积拿不了w，但是又有空余，这就造成了浪费。
比如第一个例子当中，p和f是33和27。s和w是5和6，假设我们33先拿，我们优先拿5，拿了6个刚好拿完，这时候的用了30的体积，剩下的3点体积就浪费了。这时候27拿6的话就只能拿4个，于是总共只能拿6 4=10个铁锭。但实际上我们33可以拿3个5和3个6，这样刚好可以把33体积全部用完，27就拿剩下的3个5以及2个6，也可以把体积拿完，这样我们实际上一共可以拿6 5 = 11个铁锭，比上面的做法更优。
但是这个问题似乎并不是不可以解决的，比如刚才，我们拿了6个5之后发现有多余，我们可以先拿6个5，发现多余了3。为了把空间尽可能用起来，我们可以把已经拿的5去换6。6和5相差一点体积，我们多了3点体积，所以可以把3个5换成6。这样刚好就可以得到答案那个结果。
稍微想了一下，好像没有反例。于是写了代码提交，错了。我找了一下错误的数据是这个：
5130
716
82
按照我们刚才的方法来看，我们51先拿的话，直接可以把16个2全部拿完，之后剩下了19点空间，我们可以拿2个8。剩下的30拿3个8，于是可以一共可以拿16 2 3 = 21个铁锭。
但是这个答案是错的，因为51和30这两个背包都没有用完。51浪费了5，30浪费了6，这非常可惜。如果我们只拿15个2，然后拿3个7，这样就可以把51全部装满。之后30这个包可以装1个2和3个8，这样我们可以拿22个铁锭。
感觉好像又只是一种特殊情况，如果我们可以想一个机制来解决这种情况是不是就可以AC这道题了？
很遗憾，这种特殊情况很难解决，因为对于s商品可以一次性全部拿完的情况，我们很难判断每一个包究竟拿多少才可以达到最优。也就是说贪心法从根本上就是不可行的，这是出题人留下的诱饵，给你一种好像可以解，你再多努努力就可以了的错觉。
回头用枚举发现了贪心法不可解之后当然要回头了，把贪心这个方法堵死了之后，其实这道题的解法就很明显了。非常简单，就是枚举。
我们屡一下刚才发现的信息，首先只有两种商品，也只有两个背包，两个商品的价值一样，我们希望最后受益最大。那么没的说，我们肯定是希望能尽可能得多装商品。我们假设p这个包装了x个s，那么它会装多少个w？答案是能装多少装多少。
同样我们已经知道了p装了x个s和y个w，f这个包怎么装？当然是优先装体积更小的s，能装多少装多少。如果还有空余再装w，再能装多少装多少……所以我们会发现，p这个包拿s的数量确定了之后，整个拿取的方案也就确定了。我们枚举这个x就行了。
惊不惊喜意不意外，这题就是这么简单。但是如果一开始走错了路走到贪心法上去了，你可能做一下午也做不出来。而且这题也很阴险，给了1e4组测试数据，要枚举p包装了s的数量x，这个x的数量级是1e5，两个相乘算法的数量级要1e9了。但这题给了2秒，并且枚举的常数很小，Python跑完都只用了500毫秒，实际上是不会超时的，但很多人看到这个数据范围就被吓破胆了，连我一开始也被唬了一下。
但其实这也是codeforces的常规套路，让正解的时间复杂度看起来在超时边缘，吓你一波，让你不敢写。所以有经验的选手在比赛的时候，先不管三七二十一，想到算法先写出来。之后有时间多再来想优化。
只要没有被唬住，其实是很简单的题，我们一个枚举就结束了。
t=int(input())
for_inrange(t):
p,f=list(map(int,input().split('')))
cnts,cntw=list(map(int,input().split('')))
s,w=list(map(int,input().split('')))
#我们默认让s是体积小的商品，这样方便编码
ifs>w:
s,w=w,s
cnts,cntw=cntw,cnts
#最多可以拿s的上限
most_can_take=min(cnts,p//s)
ret=0
#枚举p包拿了多少个s
foriinrange(most_can_take 1):
#剩下的就是能装多少装多少
#i开头表示p这个包装的数量，f表示随从装的数量
i_take_w=min(cntw,(p-i*s)//w)
s_left=cnts-i
w_left=cntw-i_take_w
f_take_s=min(s_left,f//s)
f_take_w=min(w_left,(f-f_take_s*s)//w)
ret=max(ret,i i_take_w f_take_s f_take_w)
print(ret)
今天的文章到这里就结束了，如果喜欢本文的话，请来一波三连，给我一点支持吧（关注、转发、点赞）。
- END -
本文始发于公众号：TechFlow，求个关注
,
