(B卷,200分)- 购物（Java & JS & Python）

题目描述

商店里有N件唯一性商品，每件商品有一个价格，第 i 件商品的价格是 ai。

一个购买方案可以是从N件商品种选择任意件进行购买（至少一件），花费即价格之和。

现在你需要求出所有购买方案中花费前K小的方案，输出这些方案的花费。

当两个方案选择的商品集合至少有一件不同，视为不同方案，因此可能存在两个方案花费相同。

输入描述

输入数据含两行：

• 第一行包含两个整数N，K，整数之间通过空格隔开。分别表示商品的个数，以及需要求得的花费个数。1 ≤ N ≤ 10000，1 ≤ K ≤ min(2^N – 1，100000)
• 第二行包含N个整数a1，a2，…，an，整数之间通过空格隔开。表示N件商品的价格。1 ≤ a1 ≤ a2 ≤ … ≤ an ≤ 10000

输出描述

按花费从小到大的顺序依次输出K行，一行一个整数。表示花费前K小的购买方案的花费。

用例

题目解析

本题其实就是要我们求解：全组合中前k小组合（按照组合之和大小排序）。

具体解析可以参考：

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 2) {
    const [n, k] = lines[0].split(" ").map(Number);
    const nums = lines[1].split(" ").map(Number);
    getResult(n, k, nums);
    lines.length = 0;
  }
});

// 算法入口
function getResult(n, m, nums) {
  nums.sort((a, b) => a - b);

  // 对于一个组合模型，其”将要产生的新组合“之和越小，则优先级越高
  // curSum + nums[nextIdx] 为 ”将要产生的新组合“之和
  const pq = new PriorityQueue(
    (a, b) => a.curSum + nums[a.nextIdx] - (b.curSum + nums[b.nextIdx])
  );

  // 空组合的和为0, 将要加入的新元素是nums[0], 即索引0的元素，其将要产生的新组合之和为 0 + nums[0]
  let c = new CombineModel(0, 0);

  for (let i = 0; i < m; i++) {
    // 打印第 i 小组合
    console.log(c.curSum + nums[c.nextIdx]);

    // c是当前最小组合模型，最小的组合模型指的是将要产生的新组合之和在对应轮次中最小
    // 如果当前组合模型c还有可合入的下一个元素，即c.nextIdx + 1 < n, 则说明可以基于当前组合模型产生一个新组合
    if (c.nextIdx + 1 < n) {
      // 基于当前组合模型产生的新组合，也是本轮最小的组合，即第 i 小组合
      pq.offer(new CombineModel(c.curSum + nums[c.nextIdx], c.nextIdx + 1));

      // 当前组合需要更新nextIdx后，重新加入优先队列
      c.nextIdx += 1;
      pq.offer(c);
    }

    // 取出优先队列中最小组合（注意这里的最小，指的是基于当前组合，将要产生的新组合之和最小）
    c = pq.poll();
  }
}

// 组合模型
class CombineModel {
  constructor(curSum, nextIdx) {
    this.curSum = curSum; // 当前组合之和
    this.nextIdx = nextIdx; // 将要被加入当前组合的新元素索引位置
  }
}

// 基于堆实现优先队列
class PriorityQueue {
  constructor(cpr) {
    this.queue = [];
    this.size = 0;
    this.cpr = cpr;
  }

  swap(i, j) {
    let tmp = this.queue[i];
    this.queue[i] = this.queue[j];
    this.queue[j] = tmp;
  }

  // 上浮
  swim() {
    let ch = this.queue.length - 1;

    while (ch !== 0) {
      let fa = Math.floor((ch - 1) / 2);

      const ch_node = this.queue[ch];
      const fa_node = this.queue[fa];

      if (this.cpr(ch_node, fa_node) < 0) {
        this.swap(ch, fa);
        ch = fa;
      } else {
        break;
      }
    }
  }

  // 下沉
  sink() {
    let fa = 0;

    while (true) {
      let ch_left = 2 * fa + 1;
      let ch_right = 2 * fa + 2;

      let ch_max;
      let ch_max_node;

      const fa_node = this.queue[fa];
      const ch_left_node = this.queue[ch_left];
      const ch_right_node = this.queue[ch_right];

      if (ch_left_node && ch_right_node) {
        // 注意这里应该要>=0，因为左边优先级高
        if (this.cpr(ch_left_node, ch_right_node) <= 0) {
          ch_max = ch_left;
          ch_max_node = ch_left_node;
        } else {
          ch_max = ch_right;
          ch_max_node = ch_right_node;
        }
      } else if (ch_left_node && !ch_right_node) {
        ch_max = ch_left;
        ch_max_node = ch_left_node;
      } else if (!ch_left_node && ch_right_node) {
        ch_max = ch_right;
        ch_max_node = ch_right_node;
      } else {
        break;
      }

      // 注意这里应该要>0，因为父优先级高
      if (this.cpr(ch_max_node, fa_node) < 0) {
        this.swap(ch_max, fa);
        fa = ch_max;
      } else {
        break;
      }
    }
  }

  // 向优先队列中加入元素
  offer(ele) {
    this.queue.push(ele);
    this.size++;
    this.swim();
  }

  // 取出最高优先级元素
  poll() {
    this.swap(0, this.queue.length - 1);
    this.size--;
    const ans = this.queue.pop();
    this.sink();
    return ans;
  }
}

Java算法源码

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int k = sc.nextInt();

    int[] nums = new int[n];
    for (int j = 0; j < n; j++) {
      nums[j] = sc.nextInt();
    }

    getResult(n, k, nums);
  }

  static class CombineModel {
    int curSum; // 当前组合之和
    int nextIdx; // 将要被加入当前组合的新元素索引位置

    public CombineModel(int curSum, int nextIdx) {
      this.curSum = curSum;
      this.nextIdx = nextIdx;
    }
  }

  public static void getResult(int n, int m, int[] nums) {
    Arrays.sort(nums);

    // 对于一个组合模型，其”将要产生的新组合“之和越小，则优先级越高
    // curSum + nums[nextIdx] 为 ”将要产生的新组合“之和
    PriorityQueue<CombineModel> pq =
        new PriorityQueue<>((a, b) -> a.curSum + nums[a.nextIdx] - (b.curSum + nums[b.nextIdx]));

    // 空组合的和为0, 将要加入的新元素是nums[0], 即索引0的元素，其将要产生的新组合之和为 0 + nums[0]
    CombineModel c = new CombineModel(0, 0);

    for (int i = 1; i <= m; i++) {
      // 打印第 i 小组合
      System.out.println(c.curSum + nums[c.nextIdx]);

      // c是当前最小组合模型，最小的组合模型指的是将要产生的新组合之和在对应轮次中最小
      // 如果当前组合模型c还有可合入的下一个元素，即c.nextIdx + 1 < n, 则说明可以基于当前组合模型产生一个新组合
      if (c.nextIdx + 1 < n) {
        // 基于当前组合模型产生的新组合，也是本轮最小的组合，即第 i 小组合
        pq.offer(new CombineModel(c.curSum + nums[c.nextIdx], c.nextIdx + 1));

        // 当前组合需要更新nextIdx后，重新加入优先队列
        c.nextIdx += 1;
        pq.offer(c);
      }

      // 取出优先队列中最小组合（注意这里的最小，指的是基于当前组合，将要产生的新组合之和最小）
      c = pq.poll();
    }
  }
}

Python算法源码

import heapq
import queue

# 输入获取
n, m = map(int, input().split())
nums = list(map(int, input().split()))


# 组合模型
class CombineModel:
    def __init__(self, curSum, nextIdx):
        self.curSum = curSum  # 当前组合之和
        self.nextIdx = nextIdx  # 将要被加入当前组合的新元素索引位置

    def __lt__(self, other):
        # 对于一个组合模型，其”将要产生的新组合“之和越小，则优先级越高
        # curSum + nums[nextIdx] 为 ”将要产生的新组合“之和
        return self.curSum + nums[self.nextIdx] < (other.curSum + nums[other.nextIdx])


# 算法入口
def getResult():
    nums.sort()

    # pq = queue.PriorityQueue()
    pq = []

    # 空组合的和为0, 将要加入的新元素是nums[0], 即索引0的元素，其将要产生的新组合之和为 0 + nums[0]
    c = CombineModel(0, 0)

    for _ in range(0, m):
        # 打印第 i 小组合
        print(c.curSum + nums[c.nextIdx])

        # c是当前最小组合模型，最小的组合模型指的是将要产生的新组合之和在对应轮次中最小
        # 如果当前组合模型c还有可合入的下一个元素，即c.nextIdx + 1 < n, 则说明可以基于当前组合模型产生一个新组合
        if c.nextIdx + 1 < n:
            # 基于当前组合模型产生的新组合，也是本轮最小的组合，即第 i 小组合
            # pq.put(CombineModel(c.curSum + nums[c.nextIdx], c.nextIdx + 1))
            heapq.heappush(pq, CombineModel(c.curSum + nums[c.nextIdx], c.nextIdx + 1))

            # 当前组合需要更新nextIdx后，重新加入优先队列
            c.nextIdx += 1
            # pq.put(c)
            heapq.heappush(pq, c)

        # 取出优先队列中最小组合（注意这里的最小，指的是基于当前组合，将要产生的新组合之和最小）
        # c = pq.get()
        if len(pq) > 0:
            c = heapq.heappop(pq)


# 算法调用
getResult()