Mat*_*nor 5 algorithm math logic computational-geometry
我接受了下周的采访,并且正在练习同样的问题.我遇到了这个问题,你能帮我解决一下吗？
有一个礼品自动售货机,你有B袋收集礼品.每个礼品自动售货机都有无限的礼品.
每台机器在时间Si秒开始丢弃礼物并且每隔Ii秒继续丢弃礼物.您可以以任何您喜欢的方式安排小袋,但一旦将它们放在一台机器下面,您就无法将其移动到另一台机器上.您需要在最短的时间内收集至少C礼品.
输入
第一行包含整数A,B,C.
第二行包含整数Si.(用空格分隔),我从1到A.
第三行包含整数Ii(用空格分隔),我从1到A.
产量
给出计算的最小时间的整数.
我认为这种方法效率很低.我认为我们可以将所有子集的基数等于B,然后选择给出最小时间的子集.
这种方法似乎是暴力,所以我正在寻找另一种替代方法.
你们中的任何人都可以帮我吗？
一种可能的方法如下：
通过逐步执行事件来同时模拟每台自动售货机。对于每台机器，计算其掉落礼物的时间并逐步执行该时间。
另外，维护所有机器的优先级队列，按照迄今为止掉落的礼物数量排序。
那么当赠品顶级机器的总和B相等时C，就是最小时间T_min。
Order of complexity: O( T_min * A * logA )