网易雷火游戏客户端笔试第三题
1 100%
2 100%
3 95%
4 5%
当然，第四题只是骗分
本来想在牛客上看看我的做法哪里有缺漏，但是目前好像还没看到谁和我的思路是一样的。
首先，把队伍分成四种类型，ab都有，仅有a，仅有b，ab都无。不妨叫做ab桶，a桶，b桶，null桶。在第一遍遍历的时候，读入每个队伍的职业分布，存入队列vec中，并根据其内容将其放入相应桶中，记录这个队伍的人数，同时记录下它在哪个桶中(无所谓用哈希表记还是用结构体，这不是重点，总之能知道哪个队伍在哪个桶里就行，哪个队伍有多少人)
然后，遍历vec，根据其所属桶，去找相应的桶。
有这么几种情况:
1.如果当前考察的队伍v属于ab桶，那么用团队人数m减去v的人数mv，得到差值d，说明还差d人。如果d＞0的话，就去null桶中做背包，若能找到若干队伍人数加起来为d，返回其id最小的即可。(比如:如果2 3 5队伍和2 4队伍都符合条件，那么返回2 3 5，这个是背包的细节，在这姑且只谈抽象的思路)，成功找到说明v能找到其他若干队伍组成团队，那么把这些队伍放入输出队列，并且给这些队伍做上标记，不管是遍历vec还是背包等都不再把这些队伍加入考察范围了。
2.同理，如果队伍v属于a桶，首先需要在b桶中遍历直到找到一个队伍v2使vm+v2m≤团队人数m。然后再根据其差值考虑是否在null桶中做背包。如果b桶找不到符合的，那说明这个队伍肯定不能匹配成团队。同样的，能有符合条件的那就记录并且放入输出队列。
3.如果队伍属于b桶，同2
4.按照这样的思路，如果当前队伍v属于null桶，看起来会很复杂，因为有可能去ab桶找，也有可能a桶和b桶各找一个。不过，我认为更优的思路应该是，遍历vec的时候如果队伍v属于null桶，就直接跳过它考察下一个队伍。举个例子，队伍3属于null桶，队伍4属于ab桶，且3和4正好能组成团队。遍历vec时跳过队伍3，去考察队伍4，根据其所属桶，我们一样能在null桶中做背包而返回队伍3，得到输入队列4 3(写到这里突然想到，是不是因为应该输出3 4而不是4 3所以差了5%，我不记得需要输出什么东西了，所以放个臀如果有大佬看出错误了可以踢我，万谢)。不用担心id问题，因为vec的id都是从小到大排列的，桶中的也是。字数有限，我在一楼阐述原因。 #雷火笔试#
类似资料：