escape on the train求助

某公司oa，当场没有做出来，一直没什么思路，来请教一下各位

可以考虑用Heap.

不必管如何排序通过，乘客会最优化处理。每次处理最近的一个乘客，然后exit自己有一个时间。如果下个乘客按照计算更早到，那么需要take math.max(exit_clock+1, arrival）

def sol(x_dist, passengers:list):
    from collections import Counter
    def dist(x1,y1,x2,y2):
        return abs(x2-x1)+abs(y2-y1)
    dists=[dist(x1, y1, x_dist, 0) for (x1,y1) in passengers ]

    dists.sort()
    print(dists)
    d=Counter(dists)
    print(d)
    res=0
    for x in d:
        res=max(res+d[x],x+d[x]-1)
    return res
sol(10, [[8,100],[9,100],[10,100],[11,100],[12,100]])

我怎么感觉这题没有那么简单？题目中说每个人每个时间单位必须移动（不准停留）。那么举个例子人在A(1,0),B (0,1)，出口在(0,0)
第一步A进入出口，但是同时B必须移动的话，只会离出口更远；这样B再想进入出口，必须再花两步？

wisdompeak2 发表于 2021-4-28 05:54
我怎么感觉这题没有那么简单？题目中说每个人每个时间单位必须移动（不准停留）。那么举个例子人在A(1,0),B ...

是的，所以二楼是错的，一楼我第一眼没看太明白后来也没再想过。

ThetaSigma14 发表于 2021-4-27 02:15
def sol(x_dist, passengers:list):
    from collections import Counter
    def dist(x1,y1,x2,y2):

sol(0,[[0,1],[1,0]]) = 2, 但应该等于3

salvadorsyc 发表于 2021-04-27 15:59:40
sol(0,,]) = 2, 但应该等于3

诶x不是>=3么

ThetaSigma14 发表于 2021-4-28 07:06
诶x不是>=3么

那就sol(0, [[3,0],[2,1],[1,2]])=5, 但我能想到最好的走法是7

ThetaSigma14 发表于 2021-4-28 07:06
诶x不是>=3么

主要是each passenger can only move up，down，left，and right， one step per time period的理解，能不能呆在原地不动。

salvadorsyc 发表于 2021-04-27 16:23:04
主要是each passenger can only move up，down，left，and right， one step per time period的理解，能不能呆在原地不动。

got it.确实有点难.....