p*****y
发帖数: 1049 | 1 有N个柜台，每个柜台处理的时间是固定的，但是不同的柜台处理的时间不一样。用
vector processTime 表示
我的前面有M个人在排队，请问我最少要等多久？算法复杂度是多少？
如果M>>N，有什么更快的办法？ |
s********d
发帖数: 162 | 2 M个人一个一个往柜台里放
每个人把每个柜台都试一遍找出最优解，这是N
全部排完是 M x N
当M >> N时， 找vector 里时间的最小公倍数
公倍数除以时间就可以放一批
一批一批放完后，
剩下的不够一批
再一个一个单独放
不知道对不对
欢迎指正
【在 p*****y 的大作中提到】
: 有N个柜台，每个柜台处理的时间是固定的，但是不同的柜台处理的时间不一样。用
: vector processTime 表示
: 我的前面有M个人在排队，请问我最少要等多久？算法复杂度是多少？
: 如果M>>N，有什么更快的办法？
|
p*****y
发帖数: 1049 | 3 可以优化到 M log N
【在 s********d 的大作中提到】
: M个人一个一个往柜台里放
: 每个人把每个柜台都试一遍找出最优解，这是N
: 全部排完是 M x N
: 当M >> N时， 找vector 里时间的最小公倍数
: 公倍数除以时间就可以放一批
: 一批一批放完后，
: 剩下的不够一批
: 再一个一个单独放
: 不知道对不对
: 欢迎指正
|
s********d
发帖数: 162 | 4 具体怎么做，可以说说么？
【在 p*****y 的大作中提到】
: 可以优化到 M log N
|
d***a
发帖数: 13752 | 5 这是给大家出的考题？
用堆就可以了。把柜台按下一次服务结束时间来构建堆，每一步从堆顶取出一个柜台，
增加服务时间后再放回堆。每步时间复杂度为log(N)，一共做M步，总的复杂度是
M log(N)。
【在 p*****y 的大作中提到】
: 可以优化到 M log N
|
A***g
发帖数: 1816 | |
S**********A
发帖数: 1 | 7 可以用贪心法做
3-approximate
【在 p*****y 的大作中提到】
: 有N个柜台，每个柜台处理的时间是固定的，但是不同的柜台处理的时间不一样。用
: vector processTime 表示
: 我的前面有M个人在排队，请问我最少要等多久？算法复杂度是多少？
: 如果M>>N，有什么更快的办法？
|
