美团9.14笔试

选择30分，编程70分

编程

第一题ac

小红R，小蓝B，小绿G在字符串上玩捉迷藏，*为空地，#为障碍物，抓捕者抓到一个就算胜利，问三人分别作为抓捕者获胜的最小步数是多少？

R****B**#G

5 5 -1

以用例为例子，这题我的思路是用map记录R的下标0， B的下标5， G的下标9

然后创建一个数组a，a[i]表示从 0 到 i 有多少个障碍物，这样一来，判断一个人能否抓到另一个人，判断从0到它的地障碍物的数量是不是一样就行了。

a[0] = 0 , a[5] = 0, a[9] = 1

R 可以抓到 B， 不能抓到G

第二题 ac

给三种宝石a,b,c的和数字x,y，其中x代表x块a宝石可以合成一块b宝石,y块b宝石可以合成一块c宝石。 问最多能凑几套，每种宝石各一种算一套。

这题我看了下大家通过率较高的作法都是二分，我直接模拟也ac了，供大家参考，

首先，最少能合成的套数是三种宝石数量最小的，

然后剩下的，看a的数量，a为0的话，因为a不能合成，所以答案就是上面的最小值，

a不为0的时候，接着看b的数量，b为0的情况，那看a能不能够合一块，能合就合

b不为0的情况，看c，c为0，看b能不能够合成，b够就先合，b不够就找a合，就这样模拟一步步，用一个循环，在里面判断，每合成一步就contine，不能合就break。

第三题 10%

有思路，来不及写，供参考。

题目是给n个点，q次询问，和x，y，其中x 代表 下一个点的value 大于这个点的value，获得x金币，下一个点的value 小于等于这个点的value， 获得y金币，。

下一行给n个数，代表下标 i 的指向

下一行给n个数，代表节点i的value

（这两个顺序可能不对）

下q行，每行两个数u， k，代表以节点u为起点，步数不大于k的情况下，所能得到金币的最大值

数据范围非常大，x y 是 2 * 10^5 ， k 达到了10^9

这题我的思路是：从起点开始遍历，记录走过的节点，和目前所获得的金币，因为这个k非常大，所以图很大概率存在环，那么我记录走过的节点，当我再次访问到这个节点的时候，说明走到环了，有环还有一个问题，这个环的价值是正的还是负的，如果是负的就没必要走了，答案在前面出现了，如果是正的，就看还得走这个环多少次，这道题走到这，最后一圈环走完，可能还余下几步，然后这答案可能存在这最后这几步中，也有可能存在最后一圈环的某一步中。要考虑的细节太多，且很难造用例，所以这个思路时间不，不知道有没有牛友有更好的思路，感谢分享。

以上。