1968. 奶牛赛跑
摘要
Title: 1968. 奶牛赛跑
Tag: 模拟、枚举、跑步比赛问题
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1968. 奶牛赛跑
-
题意
见原题
-
思路
可以通过枚举整数点，通过比较在时刻整点时的距离大小，判断领先问题，一共大约1e6个点，枚举即可
（因斜率变化，也就是速度变化的点，都是整点）为什么可以通过整点？
考虑极端情况，即两个斜率变化的点相连的线段，且两点距离为1。
考虑反证法，即不可以通过枚举整数点，那么也就是着两点之间存在另一个线在上面或下面的情况，也就是会出现一个上凸包或一个下凸包，但显然两个点只能形成一条直线，两条直线只能相交一点，所以两条直线不可能出现凸包，所以不成立，所以原假设成立。 -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35n, m = map(int, input().split())
N = int(1e6 + 10)
a = [0] * N
b = [0] * N
s = 0 # 时刻
for i in range(n):
v, t = map(int, input().split())
while t:
s += 1
a[s] = a[s - 1] + v
t -= 1
s = 0 # 时刻
for i in range(m):
v, t = map(int, input().split())
while t:
s += 1
b[s] = b[s - 1] + v
t -= 1
ans = 0
k = 0 # 0代表两者齐头并进，1代表a领先，2代表b领先
for i in range(N):
if a[i] > b[i]:
if k == 2:
ans += 1
k = 1
elif a[i] < b[i]:
if k == 1:
ans += 1
k = 2
print(ans)