(B卷,200分)- 人气最高的店铺（Java & JS & Python）

题目描述

某购物城有m个商铺，现决定举办一场活动选出人气最高店铺。

活动共有n位市民参与，每位市民只能投一票，但1号店铺如果给该市民发放 q 元的购物补贴，该市民会改为投1号店铺。

请计算1号店铺需要最少发放多少元购物补贴才能成为人气最高店铺（即获得的票数要大于其他店铺），如果1号店铺本身就是票数最高店铺，返回0。

输入描述

第一行为小写逗号分割的两个整数n，m，其中：

• 第一个整数n表示参与的市民总数
• 第二个整数m代表店铺总数
• 1 ≤ n,m ≤ 3000

第2到n+1行，每行为小写逗号分割的两个整数p，q，表示市民的意向投票情况，其中每行的：

• 第一个整数p表示该市民意向投票给p号店铺
• 第二个整数q表示其改投1号店铺所需给予的q元购物补贴
• 1 ≤ p ≤ m
• 1 ≤ g ≤ 10^9

不考虑输入的格式问题

输出描述

1号店铺需要最少发放购物补贴金额

用例

题目解析

本题就是

的换皮题，具体解析请看该博客的。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // 市民数量, 店铺数量
  const [n, m] = (await readline()).split(",").map(Number);

  // shop_costs是一个字典，key为店铺id，value为该店铺名下的市民
  const shop_costs = {};

  // 记录所有市民中最大的改选花费，用于后面构造权值线段树
  let max_cost = 0;

  // 记录自己店铺胜选所需要的花费
  let ans = 0;

  // 获取n行输入
  for (let i = 0; i < n; i++) {
    // 店铺id, 改选自己店铺的花费
    const [shop, cost] = (await readline()).split(",").map(Number);

    // 如果改选花费为0，则说明选的就是自己店铺
    if (cost == 0 || shop == 1) continue;

    // 记录不选自己店铺的市民中最大的改选花费
    max_cost = Math.max(max_cost, cost);

    // ans记录的是自己店铺胜选所需要的花费，初始时，我们假设让所有不选自己店铺的人都改选自己店铺，那么自己店铺就获得所有选票，此时肯定胜选
    ans += cost;

    // shop_costs是一个字典，key为店铺id，value为该店铺名下的市民
    if (!shop_costs[shop]) shop_costs[shop] = [];
    shop_costs[shop].push(cost);
  }

  // scan是扫描线矩阵
  const scan = [];
  for (let costs of Object.values(shop_costs)) {
    costs.sort((a, b) => b - a);

    for (let i = 0; i < costs.length; i++) {
      if (scan.length <= i) scan.push([]);
      scan[i].push(costs[i]);
    }
  }

  // 我手中的票，初始时，假设我们想获得所有票
  let my_ticket_count = n;
  // 获得所有票的花费
  let my_ticket_cost = ans;

  // 构建权值线段树
  const tree = new WSegmentTree(max_cost);

  // 开始扫描
  for (let i = 0; i < scan.length; i++) {
    //  被扫描线扫到的都是每个店铺名下改选花费最大的市民，对于这部分市民，我们放弃
    const line = scan[i];

    for (let cost of line) {
      // 将被放弃的市民的改选费用加入权值线段树，后面如果自己店铺票数不够，还需要复活一些市民
      tree.add(1, 1, max_cost, cost);
      // 由于放弃了这部分市民，因此可以去除他们的改选花费
      my_ticket_cost -= cost;
      // 由于放弃了这部分市民，因此相应票数也要去除
      my_ticket_count -= 1;
    }

    let extra_ticket_cost = 0;
    // 此时其他店铺的选票数为i+1，因此如果我们的选票数my_ticket_count <= i+1，则无法取胜
    if (my_ticket_count <= i + 1) {
      // 我们手中总票数只有达到 i+2 张，才能战胜其他店铺，但是注意 i+2 不能超过总票数n, 因此我们还需要正确额外的 min(i+2, n) - my_ticket_count 张票
      const extra_ticket_count = Math.min(i + 2, n) - my_ticket_count;
      // 高效的求解一组数中的前x小数之和，可以基于权值线段树求解，相当于求解前extra_ticket_count小之和
      extra_ticket_cost = tree.query(1, 1, max_cost, extra_ticket_count);
    }

    // 每轮扫描线扫描后，计算其花费，保留最小花费作为题解
    ans = Math.min(ans, my_ticket_cost + extra_ticket_cost);
  }

  console.log(ans);
})();

// 权值线段树
class WSegmentTree {
  constructor(n) {
    // 线段树都要开4n的空间
    this.count = new Array(n << 2).fill(0); // 权值树
    this.sum = new Array(n << 2).fill(0); // 和树
  }

  /**
   * 向权值线段树中加入一个数
   * @param {*} k 当前所在的线段树节点的序号
   * @param {*} l 前所在的线段树节点 对应的区间范围的左边界
   * @param {*} r 当前所在的线段树节点 对应的区间范围的右边界
   * @param {*} val 要加入权值线段数的数
   */
  add(k, l, r, val) {
    // 到达叶子节点
    if (l == r) {
      this.count[k] += 1;
      this.sum[k] += val;
      return;
    }

    // 节点k的左子节点序号
    const lson = k << 1; // 相当于 2 * k
    const rson = (k << 1) | 1; // 相当于 2 * k + 1

    // 左子节点对应区间范围[l, mid]
    // 右子节点对应区间范围[mid+1, r]
    const mid = (l + r) >> 1;

    if (val <= mid) {
      // 要加入的数val，在左子节点区间范围内
      this.add(lson, l, mid, val);
    } else {
      // 要加入的数val，在右子节点区间范围内
      this.add(rson, mid + 1, r, val);
    }

    // 回溯统计
    this.count[k] = this.count[lson] + this.count[rson];
    this.sum[k] = this.sum[lson] + this.sum[rson];
  }

  /**
   * 求解前rank小数之和
   * @param {*} k 当前所在的线段树节点的序号
   * @param {*} l 当前所在的线段树节点 对应的区间范围的左边界
   * @param {*} r 当前所在的线段树节点 对应的区间范围的右边界
   * @param {*} rank 求解前rank小数之和的rank值
   * @returns 前rank小数之和
   */
  query(k, l, r, rank) {
    // 到达叶子节点
    if (l == r) {
      return rank * l;
    }

    // 节点k的左子节点序号
    const lson = k << 1;
    // 节点k的右子节点序号
    const rson = (k << 1) | 1;

    // 左子节点对应区间范围[l, mid]
    // 右子节点对应区间范围[mid+1, r]
    const mid = (l + r) >> 1;

    // this.count统计的是某区间范围内元素的数量，这些数量累加起来就是对应元素的排名
    if (this.count[lson] < rank) {
      // 如果左子节点的元素数量 < rank，那么说明前rank个数，还有部分在右子节点中
      return (
        this.sum[lson] + this.query(rson, mid + 1, r, rank - this.count[lson])
      );
    } else if (this.count[lson] > rank) {
      // 如果左子节点的元素数量 > rank，那么说明前rank个数都在左子节点中，需要继续分解
      return this.query(lson, l, mid, rank);
    } else {
      // 如果左子节点元素数量 == rank，那么说明前rank个数就是左子节点内的元素，此时要求前rank小数之和，其实就是this.sum[lson]
      return this.sum[lson];
    }
  }
}

Java算法源码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

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

    // 市民数量
    int n = sc.nextInt();
    // 店铺数量
    int m = sc.nextInt();

    // shop_costs是一个字典，key为店铺id，value为该店铺名下的市民
    HashMap<Integer, ArrayList<Integer>> shop_costs = new HashMap<>();

    // 记录所有市民中最大的改选花费，用于后面构造权值线段树
    int max_cost = 0;
    // 记录自己店铺胜选所需要的花费
    long ans = 0;

    // 获取n行输入
    for (int i = 0; i < n; i++) {
      // 店铺id, 改选自己店铺的花费
      int shop = sc.nextInt();
      int cost = sc.nextInt();

      // 如果改选花费为0，则说明选的就是自己店铺
      if (cost == 0 || shop == 1) continue;

      // 记录不选自己店铺的市民中最大的改选花费
      max_cost = Math.max(max_cost, cost);
      // ans记录的是自己店铺胜选所需要的花费，初始时，我们假设让所有不选自己店铺的人都改选自己店铺，那么自己店铺就获得所有选票，此时肯定胜选
      ans += cost;

      // shop_costs是一个字典，key为店铺id，value为该店铺名下的市民
      shop_costs.putIfAbsent(shop, new ArrayList<>());
      shop_costs.get(shop).add(cost);
    }

    // scan是扫描线矩阵
    ArrayList<ArrayList<Integer>> scan = new ArrayList<>();
    for (ArrayList<Integer> costs : shop_costs.values()) {
      costs.sort((a, b) -> b - a);

      for (int i = 0; i < costs.size(); i++) {
        if (scan.size() <= i) scan.add(new ArrayList<>());
        scan.get(i).add(costs.get(i));
      }
    }

    // 我手中的票，初始时，假设我们想获得所有票
    int my_ticket_count = n;
    // 获得所有票的花费
    long my_ticket_cost = ans;

    // 构建权值线段树
    WSegmentTree tree = new WSegmentTree(max_cost);

    // 开始扫描
    for (int i = 0; i < scan.size(); i++) {
      //  被扫描线扫到的都是每个店铺名下改选花费最大的市民，对于这部分市民，我们放弃
      ArrayList<Integer> line = scan.get(i);

      for (Integer cost : line) {
        // 将被放弃的市民的改选费用加入权值线段树，后面如果自己店铺票数不够，还需要复活一些市民
        tree.add(1, 1, max_cost, cost);
        // 由于放弃了这部分市民，因此可以去除他们的改选花费
        my_ticket_cost -= cost;
        // 由于放弃了这部分市民，因此相应票数也要去除
        my_ticket_count -= 1;
      }

      int extra_ticket_cost = 0;
      // 此时其他店铺的选票数为i+1，因此如果我们的选票数my_ticket_count <= i+1，则无法取胜
      if (my_ticket_count <= i + 1) {
        // 我们手中总票数只有达到 i+2 张，才能战胜其他店铺，但是注意 i+2 不能超过总票数n,
        // 因此我们还需要正确额外的 min(i+2, n) - my_ticket_count张票
        int extra_ticket_count = Math.min(i + 2, n) - my_ticket_count;
        // 高效的求解一组数中的前x小数之和，可以基于权值线段树求解，相当于求解前extra_ticket_count小之和
        extra_ticket_cost = tree.query(1, 1, max_cost, extra_ticket_count);
      }

      // 每轮扫描线扫描后，计算其花费，保留最小花费作为题解
      ans = Math.min(ans, my_ticket_cost + extra_ticket_cost);
    }

    System.out.println(ans);
  }
}

// 权值线段树
class WSegmentTree {
  int[] count; // 权值树
  int[] sum; // 和树

  public WSegmentTree(int n) {
    // 线段树都要开4n的空间
    this.count = new int[n << 2];
    this.sum = new int[n << 2];
  }

  /**
   * 向权值线段树中加入一个数
   *
   * @param k 当前所在的线段树节点的序号
   * @param l 当前所在的线段树节点 对应的区间范围的左边界
   * @param r 当前所在的线段树节点 对应的区间范围的右边界
   * @param val 要加入权值线段数的数
   */
  public void add(int k, int l, int r, int val) {
    // 到达叶子节点
    if (l == r) {
      this.count[k] += 1;
      this.sum[k] += val;
      return;
    }

    // 节点k的左子节点序号
    int lson = k << 1; // 相当于 2 * k
    // 节点k的右子节点序号
    int rson = k << 1 | 1; // 相当于 2 * k + 1

    // 左子节点对应区间范围[l, mid]
    // 右子节点对应区间范围[mid+1, r]
    int mid = (l + r) >> 1;

    if (val <= mid) {
      // 要加入的数val，在左子节点区间范围内
      this.add(lson, l, mid, val);
    } else {
      // 要加入的数val，在右子节点区间范围内
      this.add(rson, mid + 1, r, val);
    }

    // 回溯统计
    this.count[k] = this.count[lson] + this.count[rson];
    this.sum[k] = this.sum[lson] + this.sum[rson];
  }

  /**
   * 求解前rank小数之和
   *
   * @param k 当前所在的线段树节点的序号
   * @param l 当前所在的线段树节点 对应的区间范围的左边界
   * @param r 当前所在的线段树节点 对应的区间范围的右边界
   * @param rank 求解前rank小数之和的rank值
   * @return 前rank小数之和
   */
  public int query(int k, int l, int r, int rank) {
    // 到达叶子节点
    if (l == r) {
      return rank * l;
    }

    // 节点k的左子节点序号
    int lson = k << 1;
    // 节点k的右子节点序号
    int rson = k << 1 | 1;

    // 左子节点对应区间范围[l, mid]
    // 右子节点对应区间范围[mid+1, r]
    int mid = (l + r) >> 1;

    // this.count统计的是某区间范围内元素的数量，这些数量累加起来就是对应元素的排名
    if (this.count[lson] < rank) {
      // 如果左子节点的元素数量 < rank，那么说明前rank个数，还有部分在右子节点中
      return this.sum[lson] + this.query(rson, mid + 1, r, rank - this.count[lson]);
    } else if (this.count[lson] > rank) {
      // 如果左子节点的元素数量 > rank，那么说明前rank个数都在左子节点中，需要继续分解
      return this.query(lson, l, mid, rank);
    } else {
      // 如果左子节点元素数量 == rank，那么说明前rank个数就是左子节点内的元素，此时要求前rank小数之和，其实就是this.sum[lson]
      return this.sum[lson];
    }
  }
}

Python算法源码

# 权值线段树
class WSegmentTree:
    def __init__(self, n):
        # 线段树都要开4n的空间
        self.count = [0] * (n << 2)  # 权值树
        self.sum = [0] * (n << 2)  # 和树

    def add(self, k, l, r, val):
        """
        向权值线段树中加入一个数
        :param k: 当前所在的线段树节点的序号
        :param l: 当前所在的线段树节点 对应的区间范围的左边界
        :param r: 当前所在的线段树节点 对应的区间范围的右边界
        :param val: 要加入权值线段数的数
        """
        if l == r:  # 到达叶子节点
            self.count[k] += 1
            self.sum[k] += val
            return

        # 节点k的左子节点序号
        lson = k << 1
        # 节点k的右子节点序号
        rson = k << 1 | 1

        # 左子节点对应区间范围[l, mid]
        # 右子节点对应区间范围[mid+1, r]
        mid = (l + r) >> 1

        if val <= mid:
            # 要加入的数val，在左子节点区间范围内
            self.add(lson, l, mid, val)
        else:
            # 要加入的数val，在右子节点区间范围内
            self.add(rson, mid + 1, r, val)

        # 回溯统计
        self.count[k] = self.count[lson] + self.count[rson]
        self.sum[k] = self.sum[lson] + self.sum[rson]

    def query(self, k, l, r, rank):
        """
        求解前rank小数之和
        :param k: 当前所在的线段树节点的序号
        :param l: 当前所在的线段树节点 对应的区间范围的左边界
        :param r: 当前所在的线段树节点 对应的区间范围的右边界
        :param rank: 求解前rank小数之和的rank值
        :return: 前rank小数之和
        """
        if l == r:  # 到达叶子节点
            return rank * l

        # 节点k的左子节点序号
        lson = k << 1
        # 节点k的右子节点序号
        rson = k << 1 | 1

        # 左子节点对应区间范围[l, mid]
        # 右子节点对应区间范围[mid+1, r]
        mid = (l + r) >> 1

        # this.count统计的是某区间范围内元素的数量，这些数量累加起来就是对应元素的排名
        if self.count[lson] < rank:
            # 如果左子节点的元素数量 < rank，那么说明前rank个数，还有部分在右子节点中
            return self.sum[lson] + self.query(rson, mid + 1, r, rank - self.count[lson])
        elif self.count[lson] > rank:
            # 如果左子节点的元素数量 > rank，那么说明前rank个数都在左子节点中，需要继续分解
            return self.query(lson, l, mid, rank)
        else:
            # 如果左子节点元素数量 == rank，那么说明前rank个数就是左子节点内的元素，此时要求前rank小数之和，其实就是this.sum[lson]
            return self.sum[lson]


# 市民数量，店铺数量
n, m = map(int, input().split(","))

# 记录店铺和其名下的市民
shop_costs = {}
# 记录最大的改选花费，用于后面构造权值线段树
max_cost = 0
# 记录自己店铺胜选所需要的花费
ans = 0

# 获取n行输入
for _ in range(n):
    # 店铺id, 改选自己店铺的花费
    shop, cost = map(int, input().split(","))

    # 如果改选花费为0，则说明选的就是自己店铺
    if cost == 0 or shop == 1:
        continue

    # 记录不选自己店铺的市民中最大的改选花费
    max_cost = max(max_cost, cost)
    # ans记录的是自己店铺胜选所需要的花费，初始时，我们假设让所有不选自己店铺的人都改选自己店铺，那么自己店铺就获得所有选票，此时肯定胜选
    ans += cost

    # shop_costs是一个字典，key为店铺id，value为该店铺名下的市民
    shop_costs.setdefault(shop, [])
    shop_costs[shop].append(cost)

# scan是扫描线矩阵
scan = []

# 初始化扫描线矩阵
for costs in shop_costs.values():
    costs.sort(reverse=True)

    for i in range(len(costs)):
        if len(scan) <= i:
            scan.append([])
        scan[i].append(costs[i])

# 我手中的票，初始时，假设我们想获得所有票
my_ticket_count = n
# 获得所有票的花费
my_ticket_cost = ans

# 构建权值线段树
tree = WSegmentTree(max_cost)

# 开始扫描
for i, line in enumerate(scan):
    # 被扫描线扫到的都是每个店铺名下改选花费最大的市民，对于这部分市民，我们放弃
    for cost in line:
        tree.add(1, 1, max_cost, cost)
        # 由于放弃了这部分市民，因此可以去除他们的改选花费
        my_ticket_cost -= cost
        # 由于放弃了这部分市民，因此相应票数也要去除
        my_ticket_count -= 1

    extra_ticket_cost = 0
    # 此时其他店铺的选票数为i+1，因此如果我们的选票数my_ticket_count <= i+1，则无法取胜
    if my_ticket_count <= i + 1:
        # 我们手中总票数只有达到 i+2 张，才能战胜其他店铺，但是注意 i+2 不能超过总票数n, 因此我们还需要正确额外的 min(i+2, n) - my_ticket_count 张票
        extra_ticket_count = min(i+2, n) - my_ticket_count
        # 高效的求解一组数中的前x小数之和，可以基于权值线段树求解，相当于求解前extra_ticket_count小之和
        extra_ticket_cost = tree.query(1, 1, max_cost, extra_ticket_count)

    # 每轮扫描线扫描后，计算其花费，保留最小花费作为题解
    ans = min(ans, my_ticket_cost + extra_ticket_cost)

print(ans)