在一条生产线上,产品按照不同的质量进行排列,每个产品只能在同一方向上移动。当两个质量不同的产品相遇时,质量较低的产品将被移出生产线,如果产品质量相同,则两个产品均移除生产线。需要输出产品相遇的次数。
输入描述:
n,表示产品数量,1 <= n <= 100000。1~1000。输出描述:
在一条生产线上,从左到右依次排列着 n 个产品。每个产品都带有固定的移动方向:要么向右,要么向左。所有产品的移动速度相同。一个产品用一个非零整数表示,其绝对值代表该产品的质量,符号代表移动方向:正数表示向右移动,负数表示向左移动。
当两个相向而行的产品相遇时,称为一次相遇事件。相遇后的淘汰规则如下:
对于任意一个向左移动的产品,如果其左侧存在仍然存活的向右移动产品,它会先与左侧最近的向右移动产品相遇。根据上述规则处理完该次相遇后,如果这个向左移动的产品仍然存活,并且其左侧还有其他仍然存活的向右移动产品,则继续发生下一次相遇;否则,对这个向左移动产品的处理结束。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册