题解 | #社团主席选举#

解题思路

这是一道选举问题，可以用DFS（深度优先搜索）来解决。主要思路如下：

对于每一步，我们都有两个选择：
- 贿赂所有未贿赂者中需要最少糖果的人
- 贿赂当前得票最多的候选人的支持者中需要最少糖果的人
使用DFS遍历所有可能的贿赂组合，找到使1号候选人获胜所需的最少糖果数
关键优化：
- 使用哈希表记录每个候选人的当前票数
- 使用 visited 数组避免重复贿赂
- 当当前路径的糖果消耗已经超过已知最小值时提前终止

代码

cpp
java
python

#include <bits/stdc++.h>
using namespace std;

int n, m;
unordered_map<int, int> code_vote;
long long minCost;

// 找出当前票数最高的候选人
int findMaxVotes() {
    int maxVotes = 0, maxCode = 0;
    for(int i = m; i > 0; --i) {
        if(maxVotes < code_vote[i]) {
            maxVotes = code_vote[i];
            maxCode = i;
        }
    }
    return maxCode;
}

// 找出最容易贿赂的人
pair<int,int> findMinCandyCost(int code, const vector<int>& x, 
                              const vector<long long>& y, const vector<bool>& vis) {
    long long minAll = LLONG_MAX, minSupporter = LLONG_MAX;
    int minAllIdx = -1, minSupporterIdx = -1;
    
    for(int i = 0; i < n; ++i) {
        if(vis[i]) continue;
        if(minAll > y[i]) {
            minAll = y[i];
            minAllIdx = i;
        }
        if(x[i] == code && minSupporter > y[i]) {
            minSupporter = y[i];
            minSupporterIdx = i;
        }
    }
    return {minAllIdx, minSupporterIdx};
}

void dfs(long long cost, const vector<int>& x, const vector<long long>& y, 
        vector<bool>& vis) {
    if(cost >= minCost) return;
    
    int maxCode = findMaxVotes();
    if(maxCode == 1) {
        minCost = min(minCost, cost);
        return;
    }
    
    auto [minAllIdx, minSupporterIdx] = findMinCandyCost(maxCode, x, y, vis);
    
    // 尝试贿赂所有人中最便宜的
    if(minAllIdx != -1) {
        --code_vote[x[minAllIdx]];
        ++code_vote[1];
        vis[minAllIdx] = true;
        dfs(cost + y[minAllIdx], x, y, vis);
        vis[minAllIdx] = false;
        ++code_vote[x[minAllIdx]];
        --code_vote[1];
    }
    
    // 尝试贿赂支持者中最便宜的
    if(minSupporterIdx != -1 && minSupporterIdx != minAllIdx) {
        --code_vote[x[minSupporterIdx]];
        ++code_vote[1];
        vis[minSupporterIdx] = true;
        dfs(cost + y[minSupporterIdx], x, y, vis);
        vis[minSupporterIdx] = false;
        ++code_vote[x[minSupporterIdx]];
        --code_vote[1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    
    vector<int> x(n);
    vector<long long> y(n);
    vector<bool> vis(n, false);
    minCost = LLONG_MAX;
    code_vote.clear();
    
    for(int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
        ++code_vote[x[i]];
    }
    
    dfs(0, x, y, vis);
    cout << minCost << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static int n, m;
    static Map<Integer, Integer> codeVote;
    static long minCost;
    
    static int findMaxVotes() {
        int maxVotes = 0, maxCode = 0;
        for(int i = m; i > 0; --i) {
            int votes = codeVote.getOrDefault(i, 0);
            if(maxVotes < votes) {
                maxVotes = votes;
                maxCode = i;
            }
        }
        return maxCode;
    }
    
    static class Pair {
        int first, second;
        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
    
    static Pair findMinCandyCost(int code, int[] x, long[] y, boolean[] vis) {
        long minAll = Long.MAX_VALUE, minSupporter = Long.MAX_VALUE;
        int minAllIdx = -1, minSupporterIdx = -1;
        
        for(int i = 0; i < n; ++i) {
            if(vis[i]) continue;
            if(minAll > y[i]) {
                minAll = y[i];
                minAllIdx = i;
            }
            if(x[i] == code && minSupporter > y[i]) {
                minSupporter = y[i];
                minSupporterIdx = i;
            }
        }
        return new Pair(minAllIdx, minSupporterIdx);
    }
    
    static void dfs(long cost, int[] x, long[] y, boolean[] vis) {
        if(cost >= minCost) return;
        
        int maxCode = findMaxVotes();
        if(maxCode == 1) {
            minCost = Math.min(minCost, cost);
            return;
        }
        
        Pair p = findMinCandyCost(maxCode, x, y, vis);
        
        if(p.first != -1) {
            codeVote.put(x[p.first], codeVote.get(x[p.first]) - 1);
            codeVote.put(1, codeVote.getOrDefault(1, 0) + 1);
            vis[p.first] = true;
            dfs(cost + y[p.first], x, y, vis);
            vis[p.first] = false;
            codeVote.put(x[p.first], codeVote.get(x[p.first]) + 1);
            codeVote.put(1, codeVote.get(1) - 1);
        }
        
        if(p.second != -1 && p.second != p.first) {
            codeVote.put(x[p.second], codeVote.get(x[p.second]) - 1);
            codeVote.put(1, codeVote.getOrDefault(1, 0) + 1);
            vis[p.second] = true;
            dfs(cost + y[p.second], x, y, vis);
            vis[p.second] = false;
            codeVote.put(x[p.second], codeVote.get(x[p.second]) + 1);
            codeVote.put(1, codeVote.get(1) - 1);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        
        int[] x = new int[n];
        long[] y = new long[n];
        boolean[] vis = new boolean[n];
        minCost = Long.MAX_VALUE;
        codeVote = new HashMap<>();
        
        for(int i = 0; i < n; ++i) {
            x[i] = sc.nextInt();
            y[i] = sc.nextLong();
            codeVote.put(x[i], codeVote.getOrDefault(x[i], 0) + 1);
        }
        
        dfs(0, x, y, vis);
        System.out.println(minCost);
    }
}

from collections import defaultdict

def find_max_votes():
    max_votes = 0
    max_code = 0
    for i in range(m, 0, -1):
        if max_votes < code_vote[i]:
            max_votes = code_vote[i]
            max_code = i
    return max_code

def find_min_candy_cost(code):
    min_all = float('inf')
    min_supporter = float('inf')
    min_all_idx = -1
    min_supporter_idx = -1
    
    for i in range(n):
        if vis[i]:
            continue
        if min_all > y[i]:
            min_all = y[i]
            min_all_idx = i
        if x[i] == code and min_supporter > y[i]:
            min_supporter = y[i]
            min_supporter_idx = i
            
    return min_all_idx, min_supporter_idx

def dfs(cost):
    global min_cost
    
    if cost >= min_cost:
        return
        
    max_code = find_max_votes()
    if max_code == 1:
        min_cost = min(min_cost, cost)
        return
        
    min_all_idx, min_supporter_idx = find_min_candy_cost(max_code)
    
    if min_all_idx != -1:
        code_vote[x[min_all_idx]] -= 1
        code_vote[1] += 1
        vis[min_all_idx] = True
        dfs(cost + y[min_all_idx])
        vis[min_all_idx] = False
        code_vote[x[min_all_idx]] += 1
        code_vote[1] -= 1
        
    if min_supporter_idx != -1 and min_supporter_idx != min_all_idx:
        code_vote[x[min_supporter_idx]] -= 1
        code_vote[1] += 1
        vis[min_supporter_idx] = True
        dfs(cost + y[min_supporter_idx])
        vis[min_supporter_idx] = False
        code_vote[x[min_supporter_idx]] += 1
        code_vote[1] -= 1

n, m = map(int, input().split())
x = []
y = []
vis = [False] * n
min_cost = float('inf')
code_vote = defaultdict(int)

for _ in range(n):
    xi, yi = map(int, input().split())
    x.append(xi)
    y.append(yi)
    code_vote[xi] += 1

dfs(0)
print(min_cost)

算法及复杂度分析

算法：深度优先搜索（DFS）+ 贪心策略
时间复杂度： $\mathcal{O}(2^n)$ - 最坏情况下需要尝试所有可能的贿赂组合
空间复杂度： $\mathcal{O}(n)$ - 需要存储投票信息和递归调用栈