娱乐 每 日 算 法 挑 战 【第7期】

[Mr.K 018]

第7期来啦！

总感觉是不是搞点宣传会比较好呢……

今天的题目来自QQ群：

不要停下来啊！

 

召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

[yhz012]

女人唱歌.jpg

让我看看这题

最暴力的做法就是直接求团长到车上的时间和追兵到车上时间就可以了吧？ 问题见下面回复

 

跑路时间是 (c - a) / s1， (c - b) / s2

障碍时间追兵的很好算，直接n * t2就完了，团长的需要处理下，不过直接线性扫过去就好了吧，大于a的就计入

四月 16, 2020，由yhz012修改

[Mr.K 018]

1 分钟前, yhz012 说道:

女人唱歌.jpg

Kibo no hana~

[魍魉QAQ]

这道题算法好像不难哎。。

[Mr.K 018]

刚刚, 魍魉QAQ 说道:

这道题算法好像不难哎。。

不难啊~

大众口味

[yhz012]

5 分钟前, Mr.K 018 说道:

Kibo no hana~

样例里面团长跑步速度5米每秒，不要停下来啊

[魍魉QAQ]

11 分钟前, yhz012 说道:

女人唱歌.jpg

让我看看这题

最暴力的做法就是直接求团长到车上的时间和追兵到车上时间就可以了吧？

 

跑路时间是 (c - a) / s1， (c - b) / s2

障碍时间追兵的很好算，直接n * t2就完了，团长的需要处理下，不过直接线性扫过去就好了吧，大于a的就计入

应该不能直接比吧？

人物移动速度不知道谁快，翻越障碍的时间也不清楚

万一被追击者的速度大于追击者

会不会出现被追击者最后反超追击者的情况呢？

感觉你想简单了嗼

[yhz012]

1 分钟前, 魍魉QAQ 说道:

应该不能直接比吧？

人物移动速度不知道谁快，翻越障碍的时间也不清楚

万一被追击者的速度大于追击者

会不会出现被追击者最后反超追击者的情况呢？

感觉你想简单了嗼

意识到了问题，可能出现先追上了结果因为后面的障碍又逃掉了的情况

不过这样的话首先判断障碍时间，如果障碍时间团长比追击者慢，那上面的方法肯定不影响了

如果障碍时间团长更快的话，最暴力的方法就是从c点往前到a点，每个障碍判断一次，只要有被追上的情况就女人唱歌了.jpg

四月 16, 2020，由yhz012修改

[魍魉QAQ]

7 分钟前, yhz012 说道:

意识到了问题，可能出现先追上了结果因为后面的障碍又逃掉了的情况

不过这样的话首先判断障碍时间，如果障碍时间团长比追击者慢，那上面的方法肯定不影响了

如果障碍时间团长更快的话，最暴力的方法就是从c点往前到a点，每个障碍判断一次，只要有被追上的情况就女人唱歌了.jpg

为什么被追击者翻越障碍时间比追击者满就不影响了呢？

中间的距离也不知道，翻越障碍的时间差很可能在中间跑步的时候补回来嗼

[宗周居士SP]

还以为是编程那个算法……

[魍魉QAQ]

刚刚, 宗周居士SP 说道:

还以为是编程那个算法……

大佬要编程也可以试试啊，语言不限，伪代码也行

[yhz012]

34 分钟前, 魍魉QAQ 说道:

为什么被追击者翻越障碍时间比追击者满就不影响了呢？

团长如果翻障碍更慢的话，……

………………

我知道你的意思了，可能是团长虽然跑得快，但是翻越障碍慢…………

所以先判速度和翻越时间

如果团长速度慢，但是翻越时间短，那就从c点往回a点判，应该也有可以加速的操作

如果团长速度快，而且翻越时间短，那别问了，团长肯定逃掉了

如果团长速度快，但是翻越时间长，那就从a点开始往c点判，这部分应该还是有一些可以加速的操作的

如果团长速度慢，而且翻越时间长，直接看最后能不能上车就可以了

 

两个需要逐点判断的加速可以这样做

首先能求出来团长到车之间的障碍数m，当然追兵到团长之间的障碍数也就直接n-m就好了

首先假定团长到车之间都没障碍，能求到团长时间和追兵时间分别列为time1和time2

 

如果团长速度慢，但是翻越时间短，这种情况下，如果time1已经小于time2了，那肯定跑了

否则能拿到时间差timeDiff，timeDiff / (t2 - t1)就是团长为了逃掉所需要的障碍数，和m比较一下，如果m大，那就逃掉了，否则女人唱歌.jpg

 

同理，对于团长速度快，但是翻越时间长，这种情况下，如果time1 已经大于time2了，那就女人唱歌.jpg

否则能拿到时间差timeDiff， timeDiff / (t1 - t2)是团长逃掉所能最大容纳的障碍数，和m比较一下，如果m小，那就逃掉了，否则女人唱歌.jpg

 

总共用的时间O(n)就可以了（这里我假设给的障碍是无序的，不然可以用二分查找拉到O(log n)的水平）

 

所以实际上其实可以写到一起

import numpy as np

m = np.sum(np.asarray(Block) > a)
dist1 = c - a
dist2 = c - b

time1 = dist1 / s1
time2 = dist2 / s2 + t2 * (n - m)

timeDiff = time1 - time2
tDiff = t1 - t2

if timeDiff < 0 and tDiff < 0:
  return True
elif timeDiff > 0 and tDiff > 0:
  return False
elif tDiff == 0:
  return (timeDiff > 0)

num = np.abs(timeDiff / tDiff)
if num > m:
  return (timeDiff < 0)
else:
  return (timeDiff > 0)

 

四月 16, 2020，由yhz012修改

[NianRuoshui]

因为地球是圆的所以早晚会遇上

[yhz012]

1 分钟前, NianRuoshui 说道:

因为地球是圆的所以早晚会遇上

我看过剧透，最后都是女人唱歌男人死.jpg，所以肯定会追上（

[NianRuoshui]

9 分钟前, yhz012 说道:

我看过剧透，最后都是女人唱歌男人死.jpg，所以肯定会追上（

是必定结果，不用算了（

[魍魉QAQ]

13 分钟前, NianRuoshui 说道:

因为地球是圆的所以早晚会遇上

他们不是在坐标上面跑吗？