目录
华为OD机试 2023B卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
某城市有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 的情况不会出现。
六、Java算法源码
public class OdTest02 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取市民总数n和商店总数m
String[] firstLine = scanner.nextLine().split(",");
int n = Integer.parseInt(firstLine[0]);
int m = Integer.parseInt(firstLine[1]);
// 如果只有一个商店，那么1号商店自然最受欢迎，无需补贴
if (m == 1) {
System.out.println(0);
scanner.close();
return;
}
// 存储所有市民的详细信息
List<Citizen> allCitizens = new ArrayList<>();
// 存储每个非1号商店的投票者信息（按补贴金额排序）
List<Citizen>[] votersPerOtherStore = new ArrayList[m + 1];
for (int i = 0; i <= m; i++) {
votersPerOtherStore[i] = new ArrayList<>();
}
// 记录1号商店的初始票数
int initialStore1Votes = 0;
// 读取n行市民的投票意向和补贴金额
for (int i = 0; i < n; i++) {
String[] citizenData = scanner.nextLine().split(",");
int p = Integer.parseInt(citizenData[0]); // 商店编号
int q = Integer.parseInt(citizenData[1]); // 补贴金额
Citizen citizen = new Citizen(i, p, q);
allCitizens.add(citizen);
if (p == 1) {
initialStore1Votes++;
} else {
votersPerOtherStore[p].add(citizen);
}
}
scanner.close();
// 对每个非1号商店的投票者按补贴金额升序排序
for (int i = 2; i <= m; i++) {
Collections.sort(votersPerOtherStore[i]);
}
// 检查1号商店是否已经是最受欢迎的
// 首先计算所有商店的初始票数
int[] currentTotalVotes = new int[m + 1];
for (Citizen c : allCitizens) {
currentTotalVotes[c.initialStore]++;
}
int maxOtherStoreInitialVotes = 0;
if (m > 1) { // 只有当商店总数大于1时，才需要比较
for (int j = 2; j <= m; j++) {
maxOtherStoreInitialVotes = Math.max(maxOtherStoreInitialVotes, currentTotalVotes[j]);
}
}
// 如果n=0（没有市民），或者1号商店票数已严格大于其他任何商店
if (n == 0 || (currentTotalVotes[1] > maxOtherStoreInitialVotes && m > 1) || (m == 1 && n > 0) ) {
if (n==0 && m>1 && currentTotalVotes[1] == 0 && maxOtherStoreInitialVotes == 0){
// 特殊情况：没有市民，所有商店票数都为0，1号商店并非严格领先
// 但题目约定最少补贴，如果此时1号商店是0票，其他也是0票，则无需补贴就能成为“之一”，但不是“严格超过”
// 这种情况根据题意应该输出0，因为无需任何操作，它已经是“并列第一”
// 但为了“超过”，至少需要一票，这取决于如何理解“最受欢迎”
// 按“超过其他所有商店”，则如果大家都0票，它不算超过。
// 题目1<=n,m，所以 n=0 不会发生。
} else {
System.out.println(0);
return;
}
}
long minOverallSubsidy = Long.MAX_VALUE;
// 迭代1号商店最终可能获得的票数 X (从1到n)
// X 是1号商店的目标票数，它必须严格大于其他任何商店的票数
for (int targetS1FinalVotes = 1; targetS1FinalVotes <= n; targetS1FinalVotes++) {
long currentSubsidyForThisTarget = 0;
int currentS1AcquiredVotes = initialStore1Votes; // 当前1号商店已获得的票数
// 记录在本轮迭代中，为了达到目标X，已经被拉拢的市民的ID，防止重复计算补贴
Set<Integer> bribedCitizenIdsInThisRound = new HashSet<>();
// 临时存储其他商店的投票者列表，因为在计算过程中会“拿走”一些投票者
// 我们从 votersPerOtherStore 复制，因为它已经为每个商店排好序了
List<Citizen>[] tempVotersPerOtherStore = new ArrayList[m + 1];
for(int i = 0; i <=m; i++) {
tempVotersPerOtherStore[i] = new ArrayList<>();
if (i >= 2 && i < votersPerOtherStore.length) { // 只复制其他商店
for(Citizen c : votersPerOtherStore[i]){
tempVotersPerOtherStore[i].add(c); // 浅拷贝Citizen对象即可
}
}
}
// 阶段1: 强制拉拢，确保其他商店的票数严格小于 targetS1FinalVotes
// 即，其他商店的票数最多为 targetS1FinalVotes - 1
for (int storeIdx = 2; storeIdx <= m; storeIdx++) {
int currentVotesForStoreIdx = 0; // 需要重新计算，因为tempVotersPerOtherStore是干净的初始状态
for(Citizen c : tempVotersPerOtherStore[storeIdx]){ // tempVotersPerOtherStore[storeIdx] 是初始投票给storeIdx的人
if(!bribedCitizenIdsInThisRound.contains(c.id)){ // 只计算尚未被拉拢的人
currentVotesForStoreIdx++;
}
}
// 需要从 storeIdx 拉拢的票数，使其票数 <= targetS1FinalVotes - 1
int numToBribeMandatorily = currentVotesForStoreIdx - (targetS1FinalVotes - 1);
if (numToBribeMandatorily > 0) {
// 从该商店的投票者中（已按补贴金额排序）选择最便宜的进行拉拢
// tempVotersPerOtherStore[storeIdx] 包含的是最初投给 storeIdx 的人
// 我们要从中选出 numToBribeMandatorily 个最便宜的
List<Citizen> candidatesFromStoreIdx = new ArrayList<>();
for(Citizen c : votersPerOtherStore[storeIdx]){ // 从原始排序列表选择
if(!bribedCitizenIdsInThisRound.contains(c.id)){
candidatesFromStoreIdx.add(c);
}
}
// candidatesFromStoreIdx 已经是按成本排序的
int bribedCount = 0;
for (int k = 0; k < candidatesFromStoreIdx.size() && bribedCount < numToBribeMandatorily; k++) {
Citizen citizenToBribe = candidatesFromStoreIdx.get(k);
// 确保没有重复拉拢 (虽然上面的筛选已经做了一部分，这里是双重保险)
if (!bribedCitizenIdsInThisRound.contains(citizenToBribe.id)) {
currentSubsidyForThisTarget += citizenToBribe.subsidyCost;
currentS1AcquiredVotes++;
bribedCitizenIdsInThisRound.add(citizenToBribe.id);
bribedCount++;
}
}
}
}
// 阶段 2: 收集所有还未被拉拢的、且初始不投给1号店的市民，作为潜在的拉拢对象
List<Citizen> availablePoolForBribing = new ArrayList<>();
for (Citizen citizen : allCitizens) {
if (citizen.initialStore != 1 && !bribedCitizenIdsInThisRound.contains(citizen.id)) {
availablePoolForBribing.add(citizen);
}
}
// 按补贴金额排序
Collections.sort(availablePoolForBribing);
// 阶段 3: 如果1号商店的票数仍未达到 targetS1FinalVotes，则从可用池中继续拉拢最便宜的
int additionalVotesNeededForS1 = targetS1FinalVotes - currentS1AcquiredVotes;
if (additionalVotesNeededForS1 > 0) {
if (additionalVotesNeededForS1 > availablePoolForBribing.size()) {
// 可用池中的人数不足以使1号商店达到目标票数，说明此 targetS1FinalVotes 不可行
continue; // 跳过当前 targetS1FinalVotes，尝试下一个更大的目标票数
}
for (int k = 0; k < additionalVotesNeededForS1; k++) {
Citizen citizenToBribe = availablePoolForBribing.get(k);
currentSubsidyForThisTarget += citizenToBribe.subsidyCost;
currentS1AcquiredVotes++;
// bribedCitizenIdsInThisRound.add(citizenToBribe.id); // 在池中时已保证不重复
}
}
// 检查最终1号商店的票数是否真的达到了目标，并且确实超过了其他所有商店
// （其他商店的票数已在阶段1被强制减少）
if (currentS1AcquiredVotes >= targetS1FinalVotes) {
// 验证其他商店票数是否 < targetS1FinalVotes
boolean conditionMet = true;
for (int storeIdx = 2; storeIdx <= m; storeIdx++) {
int otherStoreFinalVotes = 0;
for (Citizen c : allCitizens) {
if (c.initialStore == storeIdx && !bribedCitizenIdsInThisRound.contains(c.id) && ! (initialStore1Votes > 0 && c.initialStore == 1 && bribedCitizenIdsInThisRound.contains(c.id) )) {
// 上面的条件有点复杂，因为bribedCitizenIdsInThisRound是给S1的。
// 正确的计算方式是：storeIdx的原始票数 - 那些从storeIdx被拉拢到S1的票数
otherStoreFinalVotes = 0; // 重新计算
List<Citizen> originalVotersOfStoreIdx = votersPerOtherStore[storeIdx]; // 初始投给storeIdx的人
if (originalVotersOfStoreIdx == null) originalVotersOfStoreIdx = new ArrayList<>();
for(Citizen cOriginal : originalVotersOfStoreIdx){
if(!bribedCitizenIdsInThisRound.contains(cOriginal.id)){
otherStoreFinalVotes++;
}
}
}
}
if (otherStoreFinalVotes >= targetS1FinalVotes) {
conditionMet = false;
break;
}
}
if(conditionMet){
minOverallSubsidy = Math.min(minOverallSubsidy, currentSubsidyForThisTarget);
}
}
}
System.out.println(minOverallSubsidy);
}
}
// 定义一个类来存储市民的信息
class Citizen implements Comparable<Citizen> {
int id; // 市民的原始索引/编号
int initialStore; // 市民初始投票的商店编号
int subsidyCost; // 让该市民改投1号商店所需支付的补贴金额
public Citizen(int id, int initialStore, int subsidyCost) {
this.id = id;
this.initialStore = initialStore;
this.subsidyCost = subsidyCost;
}
// 实现Comparable接口，方便按补贴金额排序
@Override
public int compareTo(Citizen other) {
return Integer.compare(this.subsidyCost, other.subsidyCost);
}
@Override
public String toString() {
return "Citizen{" +
"id=" + id +
", p=" + initialStore +
", q=" + subsidyCost +
'}';
}
}
七、效果展示
1、输入
3,3
2,10
2,15
3,25
2、输出
35
3、说明
选择发放10+15，抢2号店铺手中的票，总共需要发放35元补贴（3号店铺1票、1号店铺2票，1号店铺胜出）
所以最少发放35元补贴。
🏆下一篇：华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】，感谢fly晨发现这个问题，并提供更优质的算法
🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
扫一扫
42万+
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
