专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。
一、题目描述
某城市有m个商店和n位市民。
现在要举办一场活动，通过投票来选出最受欢迎的商店。
每位市民只能投一票，他们将根据自己的喜好为指定的商店投票。
然而，1号商店有一个特殊的优势，它可以给每位市民发放补贴，使他们改变投票意向，投票给1号商店。
请你计算出，1号商店为了成为最受欢迎的商店（即获得的票数超过其它所有商店），需要发放多少金额的补贴。
如果1号商店已经是最受欢迎的商店，则输出0。
二、输入描述
第一行输入两个整数n和m，以逗号隔开，分别表示市民总数和商店总数。1 <= n，m <= 3000。
接下来的n行，每行输出两个整数p和q，以逗号隔开，其中p表示该市民初步想要投票给p号商店，q表示为了让该市民改投1号商店需要支付的补贴金额。
三、输出描述
输出一个整数，表示1号商店为了成为最受欢迎的商店，需要发放的最少补贴金额。
四、测试用例
测试用例1
1、输入
5,5
2,10
3,20
4,30
5,40
5,90
2、输出
50
3、说明
如果选择发放10+20+30，抢2、3、4号店铺手中的票，总共需要发放60元补贴（5号店铺2票、1号店铺3票，1号店铺胜出）
如果选择发放10+40，抢2、5号店铺手中的票，总共需要发放50元补贴（5号店铺1票、1号店铺2票，1号店铺胜出）
所以最少发放50元补贴
测试用例2
1、输入
5,5
2,10
3,20
4,30
5,80
5,90
2、输出
60
3、说明
选择发放10+20+30，抢2、3、4号店铺手中的票，总共需要发放60元补贴（5号店铺2票、1号店铺3票，1号店铺胜出）
所以最少发放60元补贴
五、解题思路
核心思想是迭代1号商店最终可能达成的“获胜票数”，我们称之为 targetS1FinalVotes。这个目标票数 X 的范围是从1到市民总数 n。对于每一个可能的 X：
- 初始化：
- currentSubsidyForThisTarget = 0: 当前目标 X 下的总补贴。
- currentS1AcquiredVotes = initialStore1Votes: 1号商店当前拥有的票数，初始为其原始票数。
- bribedCitizenIdsInThisRound = new HashSet<>(): 清空已拉拢市民集合。
- 确保其他商店票数达标
- 目标是让1号商店以 X 票获胜，这意味着其他所有商店 j ( j != 1) 的票数必须严格少于 X，即最多只能有 X-1 票。
- 遍历每个其他商店 j：
- 计算商店 j 当前拥有的（未被拉拢的）票数。
- 如果商店 j 的票数 count_j >= X，则必须从商店 j 拉拢 count_j - (X - 1) 个市民。
- 从 votersPerOtherStore[j]（已按补贴金额排序）中选择补贴金额最低的、且尚未被拉拢的市民进行拉拢。
- 累加补贴金额到 currentSubsidyForThisTarget，增加 currentS1AcquiredVotes，并将被拉拢市民的ID加入 bribedCitizenIdsInThisRound。
- 收集可供进一步拉拢的市民
- 创建一个临时的市民列表 availablePoolForBribing。
- 遍历所有市民 (allCitizens)，如果一个市民最初不投给1号店，并且在阶段一中没有被拉拢 (即其ID不在 bribedCitizenIdsInThisRound 中)，则将其加入 availablePoolForBribing。
- 按补贴金额 subsidyCost 对 availablePoolForBribing 排序。
- 确保1号商店达到目标票数 X
- 计算1号商店还需要 additionalVotesNeededForS1 = X - currentS1AcquiredVotes 票。
- 如果 additionalVotesNeededForS1 > 0：
- 检查 availablePoolForBribing 中的人数是否足够。如果不足，则当前目标 X 无法实现，跳过此 X，继续下一个 X 的迭代。
- 从 availablePoolForBribing 中选择补贴金额最低的 additionalVotesNeededForS1 个市民进行拉拢。
- 累加补贴金额，增加 currentS1AcquiredVotes。
- 更新最小总补贴：
- 在此轮迭代（针对特定 X）结束后，如果 currentS1AcquiredVotes >= X（表示1号商店达到了目标票数），并且通过阶段一的操作确保了其他所有商店的票数都严格小于 X，那么 currentSubsidyForThisTarget 就是一个可能的有效补贴总额。
- 用 currentSubsidyForThisTarget 更新 minOverallSubsidy = Math.min(minOverallSubsidy, currentSubsidyForThisTarget)。
- 初始状态检查：
- 在主循环开始前，先计算所有商店的初始票数。
- 如果1号商店的初始票数已经严格大于其他任何商店的票数（或者如果只有1个商店，或者没有市民），则最少补贴为0，直接输出并结束程序。
- 特殊情况处理：
- 如果 m=1（只有一个商店），则1号商店自然最受欢迎，成本为0。
- 题目约束 1 <= n, m，所以 n=0 的情况不会出现。
六、Python算法源码
# -*- coding: utf-8 -*-
# 定义市民类
class Citizen:
def __init__(self, id, initial_store, subsidy_cost):
self.id = id # 市民的原始索引/编号
self.initial_store = initial_store # 市民初始投票的商店编号
self.subsidy_cost = subsidy_cost # 让该市民改投1号商店需要支付的补贴金额
def __lt__(self, other): # 用于排序，按补贴金额升序
return self.subsidy_cost < other.subsidy_cost
def solve():
# 读取市民总数n和商店总数m
n_str, m_str = input().split(',')
n = int(n_str)
m = int(m_str)
# 如果只有一个商店，那么1号商店自然最受欢迎，无需补贴
if m == 1:
print(0)
return
all_citizens = [] # 存储所有市民的详细信息
# 字典，键是商店ID，值是该商店的投票者列表 (Citizen对象)
voters_per_other_store = {}
for i in range(2, m + 1):
voters_per_other_store[i] = []
initial_store1_votes = 0 # 记录1号商店的初始票数
# 读取n行市民的投票意向和补贴金额
for i in range(n):
p_str, q_str = input().split(',')
p = int(p_str) # 商店编号
q = int(q_str) # 补贴金额
citizen = Citizen(i, p, q)
all_citizens.append(citizen)
if p == 1:
initial_store1_votes += 1
else:
if p in voters_per_other_store: # 确保商店p存在于字典中
voters_per_other_store[p].append(citizen)
# 对每个非1号商店的投票者按补贴金额升序排序
for store_id in voters_per_other_store:
voters_per_other_store[store_id].sort()
# 检查1号商店是否已经是最受欢迎的
current_total_votes = [0] * (m + 1) # 索引0不用，从1到m
for c in all_citizens:
current_total_votes[c.initial_store] += 1
max_other_store_initial_votes = 0
if m > 1:
for j in range(2, m + 1):
max_other_store_initial_votes = max(max_other_store_initial_votes, current_total_votes[j])
if n == 0: # 题目约束 n >= 1
print(0)
return
# (m == 1) 的情况已在前面处理
# 如果1号商店票数已严格大于其他任何商店 (且至少有两个商店参与比较)
if (current_total_votes[1] > max_other_store_initial_votes and m > 1):
print(0)
return
min_overall_subsidy = float('inf') # 初始化为正无穷大
# 迭代1号商店最终可能获得的票数 X (从1到n)
for target_s1_final_votes in range(1, n + 1):
current_subsidy_for_this_target = 0
current_s1_acquired_votes = initial_store1_votes
bribed_citizen_ids_in_this_round = set() # 记录本轮已拉拢市民的ID
# 阶段1: 强制拉拢，确保其他商店的票数严格小于 target_s1_final_votes
for store_idx in range(2, m + 1):
# 计算 store_idx 当前未被拉拢的票数
# voters_per_other_store[store_idx] 是初始投给 store_idx 的人，已排序
# 统计当前有效的（未被本轮拉拢的）投票给 store_idx 的人数
current_votes_for_store_idx = 0
potential_bribes_from_this_store = [] # 收集本店可被拉拢的市民（未被本轮拉拢过）
# 遍历最初投给该商店的市民
original_voters_of_store = voters_per_other_store.get(store_idx, [])
for c_original in original_voters_of_store:
if c_original.id not in bribed_citizen_ids_in_this_round:
current_votes_for_store_idx +=1
potential_bribes_from_this_store.append(c_original)
# potential_bribes_from_this_store 已经是按成本排序的
num_to_bribe_mandatorily = current_votes_for_store_idx - (target_s1_final_votes - 1)
if num_to_bribe_mandatorily > 0:
bribed_count_from_store = 0
for k in range(len(potential_bribes_from_this_store)):
if bribed_count_from_store >= num_to_bribe_mandatorily:
break
citizen_to_bribe = potential_bribes_from_this_store[k]
# 确保没有重复拉拢（理论上potential_bribes_from_this_store已过滤）
if citizen_to_bribe.id not in bribed_citizen_ids_in_this_round:
current_subsidy_for_this_target += citizen_to_bribe.subsidy_cost
current_s1_acquired_votes += 1
bribed_citizen_ids_in_this_round.add(citizen_to_bribe.id)
bribed_count_from_store +=1
# 阶段 2: 收集所有还未被拉拢的、且初始不投给1号店的市民
available_pool_for_bribing = []
for citizen in all_citizens:
if citizen.initial_store != 1 and citizen.id not in bribed_citizen_ids_in_this_round:
available_pool_for_bribing.append(citizen)
available_pool_for_bribing.sort() # 按补贴金额排序
# 阶段 3: 如果1号商店的票数仍未达到 target_s1_final_votes
additional_votes_needed_for_s1 = target_s1_final_votes - current_s1_acquired_votes
if additional_votes_needed_for_s1 > 0:
if additional_votes_needed_for_s1 > len(available_pool_for_bribing):
continue # 此 targetS1FinalVotes 不可行
for k in range(additional_votes_needed_for_s1):
citizen_to_bribe = available_pool_for_bribing[k]
current_subsidy_for_this_target += citizen_to_bribe.subsidy_cost
current_s1_acquired_votes += 1
# bribed_citizen_ids_in_this_round.add(citizen_to_bribe.id) # 此处加不加都行，因为是从池里拿的
# 检查最终条件
if current_s1_acquired_votes >= target_s1_final_votes:
condition_met = True
for store_idx_check in range(2, m + 1):
other_store_final_votes = 0
original_voters_list = voters_per_other_store.get(store_idx_check, [])
for c_original in original_voters_list:
if c_original.id not in bribed_citizen_ids_in_this_round:
other_store_final_votes += 1
if other_store_final_votes >= target_s1_final_votes:
condition_met = False
break
if condition_met:
min_overall_subsidy = min(min_overall_subsidy, current_subsidy_for_this_target)
print(min_overall_subsidy if min_overall_subsidy != float('inf') else 0)
solve()
七、JavaScript算法源码
// JavaScript (Node.js environment for console input/output)
// 定义市民类
class Citizen {
constructor(id, initialStore, subsidyCost) {
this.id = id; // 市民的原始索引/编号
this.initialStore = initialStore; // 市民初始投票的商店编号
this.subsidyCost = subsidyCost; // 让该市民改投1号商店需要支付的补贴金额
}
}
// 用于排序Citizen对象的比较函数
function compareCitizens(a, b) {
return a.subsidyCost - b.subsidyCost;
}
function solve() {
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
terminal: false
});
let inputLines = [];
rl.on('line', (line) => {
inputLines.push(line);
});
rl.on('close', () => {
const [nStr, mStr] = inputLines[0].split(',');
const n = parseInt(nStr); // 市民总数
const m = parseInt(mStr); // 商店总数
if (m === 1) {
console.log(0);
return;
}
let allCitizens = []; // 存储所有市民的详细信息
// 对象，键是商店ID (字符串形式)，值是该商店的投票者列表 (Citizen对象)
let votersPerOtherStore = {};
for (let i = 2; i <= m; i++) {
votersPerOtherStore[i.toString()] = [];
}
let initialStore1Votes = 0; // 记录1号商店的初始票数
for (let i = 0; i < n; i++) {
const [pStr, qStr] = inputLines[i + 1].split(',');
const p = parseInt(pStr); // 商店编号
const q = parseInt(qStr); // 补贴金额
const citizen = new Citizen(i, p, q);
allCitizens.push(citizen);
if (p === 1) {
initialStore1Votes++;
} else {
if (votersPerOtherStore[p.toString()]) {
votersPerOtherStore[p.toString()].push(citizen);
}
}
}
for (let storeIdKey in votersPerOtherStore) {
votersPerOtherStore[storeIdKey].sort(compareCitizens);
}
let currentTotalVotes = new Array(m + 1).fill(0);
for (const c of allCitizens) {
currentTotalVotes[c.initialStore]++;
}
let maxOtherStoreInitialVotes = 0;
if (m > 1) {
for (let j = 2; j <= m; j++) {
maxOtherStoreInitialVotes = Math.max(maxOtherStoreInitialVotes, currentTotalVotes[j]);
}
}
if (n === 0) { // 题目约束 n >= 1
console.log(0);
return;
}
if (currentTotalVotes[1] > maxOtherStoreInitialVotes && m > 1) {
console.log(0);
return;
}
let minOverallSubsidy = Infinity; // 初始化为正无穷大
for (let targetS1FinalVotes = 1; targetS1FinalVotes <= n; targetS1FinalVotes++) {
let currentSubsidyForThisTarget = 0;
let currentS1AcquiredVotes = initialStore1Votes;
let bribedCitizenIdsInThisRound = new Set();
for (let storeIdx = 2; storeIdx <= m; storeIdx++) {
let currentVotesForStoreIdx = 0;
let potentialBribesFromThisStore = [];
const originalVotersOfStore = votersPerOtherStore[storeIdx.toString()] || [];
for (const c_original of originalVotersOfStore) {
if (!bribedCitizenIdsInThisRound.has(c_original.id)) {
currentVotesForStoreIdx++;
potentialBribesFromThisStore.push(c_original);
}
}
// potentialBribesFromThisStore is already sorted if original was
let numToBribeMandatorily = currentVotesForStoreIdx - (targetS1FinalVotes - 1);
if (numToBribeMandatorily > 0) {
let bribedCountFromStore = 0;
for (let k = 0; k < potentialBribesFromThisStore.length; k++) {
if (bribedCountFromStore >= numToBribeMandatorily) break;
const citizenToBribe = potentialBribesFromThisStore[k];
if (!bribedCitizenIdsInThisRound.has(citizenToBribe.id)) {
currentSubsidyForThisTarget += citizenToBribe.subsidyCost;
currentS1AcquiredVotes++;
bribedCitizenIdsInThisRound.add(citizenToBribe.id);
bribedCountFromStore++;
}
}
}
}
let availablePoolForBribing = [];
for (const citizen of allCitizens) {
if (citizen.initialStore !== 1 && !bribedCitizenIdsInThisRound.has(citizen.id)) {
availablePoolForBribing.push(citizen);
}
}
availablePoolForBribing.sort(compareCitizens);
let additionalVotesNeededForS1 = targetS1FinalVotes - currentS1AcquiredVotes;
if (additionalVotesNeededForS1 > 0) {
if (additionalVotesNeededForS1 > availablePoolForBribing.length) {
continue;
}
for (let k = 0; k < additionalVotesNeededForS1; k++) {
const citizenToBribe = availablePoolForBribing[k];
currentSubsidyForThisTarget += citizenToBribe.subsidyCost;
currentS1AcquiredVotes++;
}
}
if (currentS1AcquiredVotes >= targetS1FinalVotes) {
let conditionMet = true;
for (let storeIdxCheck = 2; storeIdxCheck <= m; storeIdxCheck++) {
let otherStoreFinalVotes = 0;
const originalVotersList = votersPerOtherStore[storeIdxCheck.toString()] || [];
for (const c_original of originalVotersList) {
if (!bribedCitizenIdsInThisRound.has(c_original.id)) {
otherStoreFinalVotes++;
}
}
if (otherStoreFinalVotes >= targetS1FinalVotes) {
conditionMet = false;
break;
}
}
if (conditionMet) {
minOverallSubsidy = Math.min(minOverallSubsidy, currentSubsidyForThisTarget);
}
}
}
console.log(minOverallSubsidy === Infinity ? 0 : minOverallSubsidy);
});
}
solve();
八、C算法源码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h> // For LONG_MAX or LLONG_MAX
// 定义市民结构体
typedef struct {
int id; // 市民的原始索引/编号
int initial_store; // 市民初始投票的商店编号
int subsidy_cost; // 让该市民改投1号商店需要支付的补贴金额
} Citizen;
// 用于qsort的比较函数，按补贴金额升序
int compare_citizens(const void *a, const void *b) {
Citizen *cA = (Citizen *)a;
Citizen *cB = (Citizen *)b;
return cA->subsidy_cost - cB->subsidy_cost;
}
// 辅助函数：检查一个id是否在集合（用数组模拟）中
int is_in_set(int id, const int *set_array, int set_size) {
for (int i = 0; i < set_size; i++) {
if (set_array[i] == id) {
return 1; // 存在
}
}
return 0; // 不存在
}
// 辅助函数：向集合（用数组模拟）中添加id
// 返回新的集合大小
int add_to_set(int id, int *set_array, int current_set_size, int max_set_size) {
if (!is_in_set(id, set_array, current_set_size) && current_set_size < max_set_size) {
set_array[current_set_size] = id;
return current_set_size + 1;
}
return current_set_size;
}
int main() {
int n, m; // 市民总数n和商店总数m
if (scanf("%d,%d\n", &n, &m) != 2) return 1; // 读取n, m
if (m == 1) {
printf("0\n");
return 0;
}
Citizen *all_citizens = (Citizen *)malloc(n * sizeof(Citizen)); // 存储所有市民信息
if (!all_citizens) return 1;
// voters_per_other_store[store_id] 是一个指向 Citizen 数组的指针
// counts_per_other_store[store_id] 是该数组中的市民数量
Citizen **voters_per_other_store = (Citizen **)malloc((m + 1) * sizeof(Citizen *));
int *counts_per_other_store = (int *)calloc(m + 1, sizeof(int)); // 初始化为0
int *capacities_per_other_store = (int *)calloc(m + 1, sizeof(int)); // 动态数组容量
if (!voters_per_other_store || !counts_per_other_store || !capacities_per_other_store) {
// 释放已分配内存
free(all_citizens);
if (voters_per_other_store) {
for(int i=2; i<=m; ++i) free(voters_per_other_store[i]);
free(voters_per_other_store);
}
free(counts_per_other_store);
free(capacities_per_other_store);
return 1;
}
for (int i = 2; i <= m; i++) { // 初始化其他商店的投票者列表
capacities_per_other_store[i] = 10; // 初始容量
voters_per_other_store[i] = (Citizen *)malloc(capacities_per_other_store[i] * sizeof(Citizen));
if (!voters_per_other_store[i]) { /* ... 错误处理和内存释放 ... */ return 1;}
counts_per_other_store[i] = 0;
}
int initial_store1_votes = 0; // 1号店初始票数
for (int i = 0; i < n; i++) {
int p, q;
if (scanf("%d,%d\n", &p, &q) != 2) { /* ... 错误处理 ... */ return 1; }
all_citizens[i].id = i;
all_citizens[i].initial_store = p;
all_citizens[i].subsidy_cost = q;
if (p == 1) {
initial_store1_votes++;
} else if (p >=2 && p <= m) { // 只处理有效范围内的其他商店
if (counts_per_other_store[p] >= capacities_per_other_store[p]) {
capacities_per_other_store[p] *= 2;
Citizen* temp = (Citizen *)realloc(voters_per_other_store[p], capacities_per_other_store[p] * sizeof(Citizen));
if(!temp) { /* ... 错误处理 ... */ return 1; }
voters_per_other_store[p] = temp;
}
voters_per_other_store[p][counts_per_other_store[p]++] = all_citizens[i];
}
}
for (int i = 2; i <= m; i++) { // 排序
if(counts_per_other_store[i] > 0) {
qsort(voters_per_other_store[i], counts_per_other_store[i], sizeof(Citizen), compare_citizens);
}
}
int *current_total_votes = (int *)calloc(m + 1, sizeof(int));
if(!current_total_votes) { /* ... 错误处理 ... */ return 1; }
for (int i = 0; i < n; i++) {
current_total_votes[all_citizens[i].initial_store]++;
}
int max_other_store_initial_votes = 0;
if (m > 1) {
for (int j = 2; j <= m; j++) {
if (current_total_votes[j] > max_other_store_initial_votes) {
max_other_store_initial_votes = current_total_votes[j];
}
}
}
if (n == 0) { // 题目约束 n >= 1
printf("0\n");
// ... 释放所有动态内存 ...
return 0;
}
if ((current_total_votes[1] > max_other_store_initial_votes && m > 1)) {
printf("0\n");
// ... 释放所有动态内存 ...
return 0;
}
long long min_overall_subsidy = LLONG_MAX; // 使用 long long 存储补贴总额
int *bribed_citizen_ids_in_this_round_arr = (int *)malloc(n * sizeof(int)); // 模拟Set
Citizen *available_pool_for_bribing_arr = (Citizen *)malloc(n * sizeof(Citizen)); // 模拟List
if(!bribed_citizen_ids_in_this_round_arr || !available_pool_for_bribing_arr) { /* ... 错误处理 ... */ return 1; }
for (int target_s1_final_votes = 1; target_s1_final_votes <= n; target_s1_final_votes++) {
long long current_subsidy_for_this_target = 0;
int current_s1_acquired_votes = initial_store1_votes;
int bribed_ids_count_this_round = 0; // 当前轮已拉拢市民数量
for (int store_idx = 2; store_idx <= m; store_idx++) {
int current_votes_for_store_idx = 0;
Citizen temp_potential_bribes[n]; // 假设n是最大可能数量
int temp_potential_bribes_count = 0;
for(int k=0; k < counts_per_other_store[store_idx]; ++k) {
Citizen c_original = voters_per_other_store[store_idx][k];
if (!is_in_set(c_original.id, bribed_citizen_ids_in_this_round_arr, bribed_ids_count_this_round)) {
current_votes_for_store_idx++;
if (temp_potential_bribes_count < n) { // 防止溢出
temp_potential_bribes[temp_potential_bribes_count++] = c_original;
}
}
}
// temp_potential_bribes 已经是按成本排序的（因为源voters_per_other_store[store_idx]是）
int num_to_bribe_mandatorily = current_votes_for_store_idx - (target_s1_final_votes - 1);
if (num_to_bribe_mandatorily > 0) {
int bribed_count_from_store = 0;
for (int k = 0; k < temp_potential_bribes_count; k++) {
if (bribed_count_from_store >= num_to_bribe_mandatorily) break;
Citizen citizen_to_bribe = temp_potential_bribes[k];
if (!is_in_set(citizen_to_bribe.id, bribed_citizen_ids_in_this_round_arr, bribed_ids_count_this_round)) {
current_subsidy_for_this_target += citizen_to_bribe.subsidy_cost;
current_s1_acquired_votes++;
bribed_ids_count_this_round = add_to_set(citizen_to_bribe.id, bribed_citizen_ids_in_this_round_arr, bribed_ids_count_this_round, n);
bribed_count_from_store++;
}
}
}
}
int available_pool_count = 0;
for (int i = 0; i < n; i++) {
if (all_citizens[i].initial_store != 1 && !is_in_set(all_citizens[i].id, bribed_citizen_ids_in_this_round_arr, bribed_ids_count_this_round)) {
if (available_pool_count < n) { // 防止溢出
available_pool_for_bribing_arr[available_pool_count++] = all_citizens[i];
}
}
}
if (available_pool_count > 0) {
qsort(available_pool_for_bribing_arr, available_pool_count, sizeof(Citizen), compare_citizens);
}
int additional_votes_needed_for_s1 = target_s1_final_votes - current_s1_acquired_votes;
if (additional_votes_needed_for_s1 > 0) {
if (additional_votes_needed_for_s1 > available_pool_count) {
continue;
}
for (int k = 0; k < additional_votes_needed_for_s1; k++) {
Citizen citizen_to_bribe = available_pool_for_bribing_arr[k];
current_subsidy_for_this_target += citizen_to_bribe.subsidy_cost;
current_s1_acquired_votes++;
// 不再需要添加到bribed_citizen_ids_in_this_round_arr，因为池已过滤
}
}
if (current_s1_acquired_votes >= target_s1_final_votes) {
int condition_met = 1;
for (int store_idx_check = 2; store_idx_check <= m; store_idx_check++) {
int other_store_final_votes = 0;
for(int k=0; k < counts_per_other_store[store_idx_check]; ++k) {
Citizen c_original = voters_per_other_store[store_idx_check][k];
if (!is_in_set(c_original.id, bribed_citizen_ids_in_this_round_arr, bribed_ids_count_this_round)) {
other_store_final_votes++;
}
}
if (other_store_final_votes >= target_s1_final_votes) {
condition_met = 0;
break;
}
}
if (condition_met) {
if (current_subsidy_for_this_target < min_overall_subsidy) {
min_overall_subsidy = current_subsidy_for_this_target;
}
}
}
}
printf("%lld\n", min_overall_subsidy == LLONG_MAX ? 0 : min_overall_subsidy);
// 释放所有动态分配的内存
free(all_citizens);
for (int i = 2; i <= m; i++) {
free(voters_per_other_store[i]);
}
free(voters_per_other_store);
free(counts_per_other_store);
free(capacities_per_other_store);
free(current_total_votes);
free(bribed_citizen_ids_in_this_round_arr);
free(available_pool_for_bribing_arr);
return 0;
}
九、C++算法源码
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <map> // 用于 voters_per_other_store
// 定义市民结构体
struct Citizen {
int id; // 市民的原始索引/编号
int initial_store; // 市民初始投票的商店编号
int subsidy_cost; // 让该市民改投1号商店需要支付的补贴金额
// 为了排序，重载小于操作符
bool operator<(const Citizen& other) const {
return subsidy_cost < other.subsidy_cost;
}
};
// 从字符串中解析逗号分隔的整数
std::pair<int, int> parse_pair(const std::string& s) {
std::stringstream ss(s);
std::string segment;
int val1, val2;
std::getline(ss, segment, ',');
val1 = std::stoi(segment);
std::getline(ss, segment, ',');
val2 = std::stoi(segment);
return {val1, val2};
}
int main() {
std::ios_base::sync_with_stdio(false); // 加速C++ IO
std::cin.tie(NULL);
std::string line;
std::getline(std::cin, line);
std::pair<int, int> nm = parse_pair(line);
int n = nm.first; // 市民总数n
int m = nm.second; // 商店总数m
if (m == 1) {
std::cout << 0 << std::endl;
return 0;
}
std::vector<Citizen> all_citizens; // 存储所有市民信息
// 使用 map 存储每个其他商店的投票者列表
//键是商店ID，值是Citizen对象的vector
std::map<int, std::vector<Citizen>> voters_per_other_store;
int initial_store1_votes = 0; // 1号店初始票数
for (int i = 0; i < n; ++i) {
std::getline(std::cin, line);
std::pair<int, int> pq = parse_pair(line);
int p = pq.first; // 商店编号
int q = pq.second; // 补贴金额
Citizen citizen = {i, p, q};
all_citizens.push_back(citizen);
if (p == 1) {
initial_store1_votes++;
} else {
voters_per_other_store[p].push_back(citizen);
}
}
// 对每个非1号商店的投票者按补贴金额升序排序
for (auto& pair_val : voters_per_other_store) {
std::sort(pair_val.second.begin(), pair_val.second.end());
}
std::vector<int> current_total_votes(m + 1, 0); // 索引0不用
for (const auto& c : all_citizens) {
current_total_votes[c.initial_store]++;
}
int max_other_store_initial_votes = 0;
if (m > 1) {
for (int j = 2; j <= m; ++j) {
max_other_store_initial_votes = std::max(max_other_store_initial_votes, current_total_votes[j]);
}
}
if (n == 0) { // 题目约束 n >= 1
std::cout << 0 << std::endl;
return 0;
}
if (current_total_votes[1] > max_other_store_initial_votes && m > 1) {
std::cout << 0 << std::endl;
return 0;
}
long long min_overall_subsidy = -1; // 用-1表示尚未找到可行方案，或用LLONG_MAX
for (int target_s1_final_votes = 1; target_s1_final_votes <= n; ++target_s1_final_votes) {
long long current_subsidy_for_this_target = 0;
int current_s1_acquired_votes = initial_store1_votes;
std::set<int> bribed_citizen_ids_in_this_round; // 记录本轮已拉拢市民的ID
// 阶段1
for (int store_idx = 2; store_idx <= m; ++store_idx) {
int current_votes_for_store_idx = 0;
std::vector<Citizen> potential_bribes_from_this_store;
if (voters_per_other_store.count(store_idx)) { // 如果该商店有投票者
const auto& original_voters_of_store = voters_per_other_store.at(store_idx);
for (const auto& c_original : original_voters_of_store) {
if (bribed_citizen_ids_in_this_round.find(c_original.id) == bribed_citizen_ids_in_this_round.end()) {
current_votes_for_store_idx++;
potential_bribes_from_this_store.push_back(c_original);
}
}
// potential_bribes_from_this_store 已经是按成本排序的
}
int num_to_bribe_mandatorily = current_votes_for_store_idx - (target_s1_final_votes - 1);
if (num_to_bribe_mandatorily > 0) {
int bribed_count_from_store = 0;
for (const auto& citizen_to_bribe : potential_bribes_from_this_store) {
if (bribed_count_from_store >= num_to_bribe_mandatorily) break;
// 再次检查，虽然理论上已过滤
if (bribed_citizen_ids_in_this_round.find(citizen_to_bribe.id) == bribed_citizen_ids_in_this_round.end()) {
current_subsidy_for_this_target += citizen_to_bribe.subsidy_cost;
current_s1_acquired_votes++;
bribed_citizen_ids_in_this_round.insert(citizen_to_bribe.id);
bribed_count_from_store++;
}
}
}
}
// 阶段 2
std::vector<Citizen> available_pool_for_bribing;
for (const auto& citizen : all_citizens) {
if (citizen.initial_store != 1 && bribed_citizen_ids_in_this_round.find(citizen.id) == bribed_citizen_ids_in_this_round.end()) {
available_pool_for_bribing.push_back(citizen);
}
}
std::sort(available_pool_for_bribing.begin(), available_pool_for_bribing.end());
// 阶段 3
int additional_votes_needed_for_s1 = target_s1_final_votes - current_s1_acquired_votes;
if (additional_votes_needed_for_s1 > 0) {
if (additional_votes_needed_for_s1 > static_cast<int>(available_pool_for_bribing.size())) {
continue;
}
for (int k = 0; k < additional_votes_needed_for_s1; ++k) {
const auto& citizen_to_bribe = available_pool_for_bribing[k];
current_subsidy_for_this_target += citizen_to_bribe.subsidy_cost;
current_s1_acquired_votes++;
// bribed_citizen_ids_in_this_round.insert(citizen_to_bribe.id); // 可选，因为是从池中取的
}
}
if (current_s1_acquired_votes >= target_s1_final_votes) {
bool condition_met = true;
for (int store_idx_check = 2; store_idx_check <= m; ++store_idx_check) {
int other_store_final_votes = 0;
if (voters_per_other_store.count(store_idx_check)) {
const auto& original_voters_list = voters_per_other_store.at(store_idx_check);
for (const auto& c_original : original_voters_list) {
if (bribed_citizen_ids_in_this_round.find(c_original.id) == bribed_citizen_ids_in_this_round.end()) {
other_store_final_votes++;
}
}
}
if (other_store_final_votes >= target_s1_final_votes) {
condition_met = false;
break;
}
}
if (condition_met) {
if (min_overall_subsidy == -1 || current_subsidy_for_this_target < min_overall_subsidy) {
min_overall_subsidy = current_subsidy_for_this_target;
}
}
}
}
// 如果从未找到可行方案（例如n=0且未被初始检查捕获），则应输出0
// 但题目约束 n>=1，所以总能找到方案（最坏情况是把所有人都拉过来）
std::cout << (min_overall_subsidy == -1 ? 0 : min_overall_subsidy) << std::endl;
return 0;
}
🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2025 B卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。
扫一扫
1202
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
