大家好,请教一个问题。假设我产品有200多个,200多个有各种各样价格。然后想做个礼盒,礼盒要求:1.每个礼盒产品数量是要6个,2、每个礼盒6个产品价格求和是在200-300区间, 符合条件的6个作为一组进行分组,不符合条件就单独拿出来不做处理。产品价格如下:
const uniform = (a: number, b: number): number => { return a + Math.floor((b - a) * Math.random()) } type Product = { id: number price: number } /** * 用双指针,每次挑选出一个价格最高的,再从价格最低的中挑出五个,相加如果价格高于300,就将r指针减一 * @param products */ const grouping = (products: Product[]) => { let l = 0 let r = products.length - 1 let ans: Product[][] = [] products.sort((a, b) => a.price - b.price) const presum: number[] = Array.from({ length: products.length + 1 }) presum[0] = 0 for (let i = 1; i <= products.length; ++i) { presum[i] = presum[i - 1] + products[i - 1].price } mainLoop: while (l + 5 <= r) { /** * 该商品的价格直接超过了300我们直接忽略他 */ if (products[r].price > 300) { --r continue } let largeCount = 1 do { let curR = r - largeCount + 1 //当largeCount取6时会导致 curL < l,所以在包一层Math.max let curL = Math.max(l + 5 - largeCount + 1, l) const sum = presum[curL] - presum[l] + presum[r + 1] - presum[curR] if (sum < 200) { /** * 小于200,再多选取一件高价商品的 */ if (largeCount + 1 < 6) ++largeCount // 6件商品都选取仍然凑不够200,没有更多解了,直接break else break mainLoop } else if (sum > 300) { /** * 和大于300剔除一件高价商品,通过--r直接把他剔除出区间 */ --r continue mainLoop } else { const cand = products.slice(l, curL).concat(products.slice(curR, r + 1)) ans.push(cand) l = curL r = curR - 1 break } } while (true) } return ans } console.log( grouping( Array.from({ length: 200 }, (_, i) => ({ id: i, price: uniform(30, 350), })) ) )