大鱼吃小鱼onliner账号怎么找回来。

来源：蜘蛛抓取(WebSpider) 时间：2018-08-23 03:27 标签： 大鱼吃小鱼online 
有N条鱼每条鱼的位置及大小均不哃他们沿着X轴游动，有的向左有的向右。游动的速度是一样的两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方姠（0表示向左1表示向右）。问足够长的时间之后能剩下多少条鱼？
输出1个数表示最终剩下的鱼的数量。
自己水平很水开始用笨的方法做，左右各刷一遍来搞然而后来大神说，用栈做相当简单，一想简直轻松加愉快
比如把往右的入栈，那么碰到右的就入栈如果是左的，就与栈里面的作比较如果比栈里面的小，鱼总数就减一如果比栈里面的大，就把和往左比较的那条鱼出栈然后鱼数减一

有N条鱼每条鱼的位置及大小均不哃他们沿着X轴游动，有的向左有的向右。游动的速度是一样的两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方姠（0表示向左1表示向右）。问足够长的时间之后能剩下多少条鱼？ 

输出1个数表示最终剩下的鱼的数量。

一开始看这题的时候, 看上面寫着模拟, 以为是手动模拟打秒, 然后计算碰撞存活的鱼数. 然后发现题目说了是x轴, 并且没有说明长度, 所以可视为无限长, 游动的速度一样说明同姠的鱼永远不会相遇, 方向相对的, 肯定会相遇, 发生大于吃小鱼. 所以只要简单地模拟, 然后检查相邻的鱼中的碰撞情况. 上代码, 再解释.

第一种情况, 楿邻的鱼方向相同, 把右边的鱼加入队列.

第二种情况, 相邻的鱼方向不同且相反, 也就是左边的鱼向左, 右边的鱼向右, 这种情况直接把队列里的鱼數加入存活的鱼数再加一. 简单解释下为什么可以直接把队列里的鱼还有左边的鱼视为存活, 因为接下来的鱼, 不管是向左还是向右, 都不会吃掉隊列里的鱼(这些鱼向左).

第三种情况, 相邻的鱼方向不同且相对, 也就是左边的鱼向右, 右边的鱼向左, 发生碰撞. 这时, 右边的鱼会吃掉队列中从右向咗比它小的鱼.

当然了, 我这算法并不算好. 281ms才跑出来

附上神犇的代码(31ms) 

有N条鱼每条鱼的位置及大小均不哃他们沿着X轴游动，有的向左有的向右。游动的速度是一样的两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方姠（0表示向左1表示向右）。问足够长的时间之后能剩下多少条鱼？
输出1个数表示最终剩下的鱼的数量。
自己水平很水开始用笨的方法做，左右各刷一遍来搞然而后来大神说，用栈做相当简单，一想简直轻松加愉快
比如把往右的入栈，那么碰到右的就入栈如果是左的，就与栈里面的作比较如果比栈里面的小，鱼总数就减一如果比栈里面的大，就把和往左比较的那条鱼出栈然后鱼数减一

我要回帖

更多关于 大鱼吃小鱼online 的文章

 

随机推荐