AcWing 1211. 蚂蚁感冒 -- Python
原题链接
简单
作者:
Duckcc
,
2021-04-05 13:56:24
,
所有人可见
,
阅读 564
基于逻辑分析
理清思路,看清题的本质
基本思想
虽然题目是,两蚂蚁相碰反向移动
但,其实只要理解为擦肩而过就行
因为虽然,蚂蚁反向行驶,但把它们身份互换,本质相同
B
A B A B A A B
|_|_|_|_| |_|_|_|_| |_|_|_|_| |_|_|_|_| 调头
B
A B A B A B A
|_|_|_|_| |_|_|_|_| |_|_|_|_| |_|_|_|_| 擦肩
1 2 3 4
**在 3 阶段时 AB都是被感染了的**
**于是,到4阶段时 A当作A看 或 把A当B看 都是无所谓的(蚂蚁相同**
接下来
因为蚂蚁移速相同,**同向在它前面走的蚂蚁是传染不到的**
同样,同向在它身后的蚂蚁,靠它自己也是传染不到的
但,**如果能碰面一只反向的蚂蚁,则能传染到同向所有身后的蚂蚁**
本身只会传染反向碰面的
Python3 代码
n = input()
line = list(map(int, input().split()))
p = line[0]
if p > 0:
q = 1
else:
q = -1 # 判断初始方向
s = 1
m = 0
x = 0
for i in line[1:]:
if i > 0:
z = 1+q
else:
z = -1+q # 同向是 2或-2 反向则加为0 而Python里 只有0为假
if p+i < 0 and not z:
s += 1 # 首先 not z 判定反向 两数相加小于0 是会碰面的
x = 1 # 用x记录是否感染同向身后的
if p-i > 0 and z: # p-i大于0 是在身后的
m += 1 # 记录同向身后个数
if x:
s += m
print(s)