刷题笔记合集🔗

人气最高的店铺

问题描述

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

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

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

输入格式

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

• 第一个整数 表示参与的市民总数
• 第二个整数 代表店铺总数
• 

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

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

不考虑输入的格式问题。

输出格式

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

样例输入

5,5
2,10
3,20
4,30
5,40
5,90

5,5
2,10
3,20
4,30
5,80
5,90

样例输出

50

60

数据范围

题解

我们有 位市民和 个店铺，1号店铺想通过"补贴"把别人原本要投给其他店铺的票抢过来，使自己成为票数最多的店。每抢一个人的票就要付出相应的金额。题目要我们算出至少需要付出多少钱。

1. 从问题本质说起

• 每个市民原本会投给某个店铺 ，如果我们给他 元，他就改投给店铺 1
• 我们的目标是让店铺 1 的票数严格大于所有其他店铺的票数之和中的最大值（即成为人气第一）

直觉上，我们需要决定"抢"哪些人的票，才能"用最少的钱"把 1号店推上第一。注意，抢不同店铺的票，对我们帮助不一样--抢票越多的店铺，往往越能降低对手的最高票，也能最快地帮助 1号店反超

2. 核心思路：枚举「1号店最终要拿到的票数」+ 强制抢 vs 可选抢

1. 统计各店初始票数
   • 先数出 1号店自己原本就有多少票
   • 记下其他每个店铺 的票数 ，并把支持店铺 的每个人需要的补贴 都放到一个小数组 groups[k] 里
2. 给每个 groups[k] 排序 & 做前缀和
   • 把每个店铺的补贴需求 按照从小到大排好序，这样如果想"抢掉"这个店铺最便宜的前 个支持者，就能在常数时间内用前缀和快速算出总补贴
3. 枚举目标票数
   • 我们假设最终想让店铺 1 拿到 票（ 从当前 开始，一直到总人数 ）
   • 对于每个其他店铺 ：
     • 本来有 票。为了让店铺 最多只能有 票（保证 1 号店能反超），我们 必须 抢走至少 张票。这部分我们称为「强制抢」，用前缀和一算就能知道最少要花多少钱
   • 把所有店铺的强制抢加起来，得到「强制抢总票数」 和「强制抢总花费」
   • 如果此时 ，说明只靠强制抢就能凑够 票，并且其它店都被压到不超过 ，答案就可以用这笔钱来更新
   • 否则，还差 票，需要从剩下没被"强制抢"的人里再任意挑最便宜的 张票，这部分称为「可选抢」。我们把所有「可选」的补贴需求放到一个数组里，排序后拿最前面 个，就能算出额外费用
4. 取所有 对应的最小花费
   • 遍历 并做上述计算，最终取最小的花费
   • 如果 一开始就超过所有其他店的票数，就直接输出 0

3. 举个小例子帮你梳理

以样例 1（5 人、5 店）为例：

• 初始票：1号店 0 票，2/3/4/5 号各 1 票，5 号多 1 票
• 对于 ：
  • 要让别人都不超过 0 票，得强制抢 2、3、4、5 各 1 票，强制抢 4 人；此时已经给自己加了 4 票，超过 1 票目标，多余。费用显然比 0 票时高，不合算
• 对于 ：
  • 别人最多只能有 1 票，不用对 2/3/4 抢，5 号店有 2 票，要抢走 1 张：强制抢花 40 元
  • 现在自己最多 0+1=1 票，还差 1 票，需要可选抢剩下最便宜的人（就是 2号店那位，10 元）
  • 总共 40+10=50 元，就能让自己变 2 票，别人都 ≤1，赢
• 更大的 只会花更多钱，所以答案是 50 元

4. 关键技巧与数据结构

• 分组排序 + 前缀和：让「抢前 个最便宜的人」能在 内求和
• 枚举目标票数：把"抢到多少票"当参数，既能兼顾"降低对手票数"和"补齐自己票数"两个需求
• 贪心挑最便宜的可选票：保证在总花费最小的前提下任意补齐差额

5. 时间复杂度

• 对每个店铺排序及前缀和：
• 枚举 （最多 次），每次要扫描 个店铺算「强制抢」，再把「可选」票排序。总计约

因为 ，最坏 量级，在 C++/Java 中能跑得很快，Python 在合适优化下也能过。

参考代码

• Python

import sys
input = sys.stdin.readline

def main():
    line = input().strip()
    if not line:
        return
    n, m = map(int, line.split(','))
    C = [0]*(m+1)
    groups = [[] for _ in range(m+1)]
    c1 = 0

    # 读入 p, q
    for _ in range(n):
        p, q = map(int, input().split(','))
        C[p] += 1
        if p == 1:
            c1 += 1
        else:
            groups[p].append(q)

    # 排序并做前缀和
    prefix = [[] for _ in range(m+1)]
    for k in range(2, m+1):
        groups[k].sort()
        pre = [0]
        for x in groups[k]:
            pre.append(pre[-1] + x)
        prefix[k] = pre

    INF = 10**30
    ans = INF

    # 枚举目标票数 t
    for t in range(c1, n+1):
        mandatory_cost = 0
        sum_req = 0
        req = [0]*(m+1)
        bad = False

        # 先算强制抢
        for k in range(2, m+1):
            ck = C[k]
            if ck > t-1:
                r = ck - (t-1)
                if r > len(groups[k]):
                    bad = True
                    break
                sum_req += r
                mandatory_cost += prefix[k][r]
                req[k] = r
                if mandatory_cost >= ans:
                    bad = True
                    break
        if bad:
            continue

        # 如果强制抢后票数已够
        if c1 + sum_req >= t:
            ans = min(ans, mandatory_cost)
            continue

        # 否则可选抢
        need = t - (c1 + sum_req)
        optional = []
        for k in range(2, m+1):
            optional.extend(groups[