一道编程信号的n变态的题

这个平台有不少公司在用, 最近频繁换账号刷, 一道很高频又感觉非常变态的题是这道, 手打不容易, 有想法说说哦signature是int minCostToShop(int[][] availableQuantities, int[][] prices, int[] requirements) {
}
是这样, 就是说你必须买几种东西, 每个可能得买多个, 而你一天只能去2个商店(当然也可以是1个), 问你买这些东西的最小cost
先从requirements说, 这是个数组, 里面包含了你必须每样东西买多少个. 比如[1, 3, 2]就是你必须买1个第0种东西, 3个第1种东西和2个第2种东西
然后prices是每种东西在每个商店的价格, 比如[[2, 3, 4], [1, 2, 3]]就是说第0种东西在第0个商店卖2, 在第1个商店卖1, 第1种东西在第0个商店卖3, 在第1个商店卖2
然后availableQuantities是每种东西在每个商店有的数量, 比如[[1, 2, 1], [2, 3, 2]]就是说第0钟东西在第0个商店有1个, 在第1个商店有2个, 第1种东西在第0个商店有2个, 在第1个商店有3个

这题有没有别的限制啊，比如只能去几天，或者有没有bundle price，不然就对每个商品从当前最低价店来买（如果买光了还没买够就去下一家），直到买够为止？
另外请问这标题该怎么断句？编程信号？信号的n？n变态？都啥意思

idealmaster 发表于 2021-5-31 01:05
这题有没有别的限制啊，比如只能去几天，或者有没有bundle price，不然就对每个商品从当前最低价店来买（如 ...

编程信号=codesignal
n变态=很变态
我猜的。。。

idealmaster 发表于 2021-5-31 01:05
这题有没有别的限制啊，比如只能去几天，或者有没有bundle price，不然就对每个商品从当前最低价店来买（如 ...

对, 其实我做了一下, 是还行, 如果明白了它的意思的话...
我在发帖的时候还不太明白它的意思...

感觉还行吧，想象一下如果只有一件商品，so let: reuqirements = 10，availableQuantities = [2,3,4,5]，prices = [8, 2, 9, 4]
就从最便宜的买起，直到买满10件，于是 cost = 3x2 + 5x4 + 2x8 = 42

拓展到n件商品，m个商店，需要把商店打乱次序，创造一个新的2D array，每个element是一个array，按price从小到大排列，index表示商品index。这里每个element推荐用linked list 便于遍历时插入：
shopsOrderedByPrice = [
{shopIndex: 1, price: 1, quantity: 2} --> {shopIndex: 0, price: 2, quantity: 1} --> ....
...
]
最后通过reuqirements走一遍，计算结果。
创建新array最耗时，估计复杂度O(n x m x log(m))。不知各大牛有没有更好解法

抱歉，您不能对匿名帖评分

背包问题，dp解决？