题解 | #拉票#_牛客博客

题目链接

拉票

题目描述

在一场有 $n$ 个人投票的选举中，每个人都隶属于一个特定的阵营。小明属于阵营 $m$ ，所有该阵营的成员都会自动投票给小明。

小明可以额外游说一个其他阵营，使得该阵营的所有成员也投票给他。为了使总票数最多，小明会选择人数最多的那个阵营进行游说。

有一个特殊情况：如果一开始所有人就都属于小明的阵营，他将不会进行任何游说。

求小明最终能获得的最大票数。

解题思路

这是一个简单的计数和查找问题。核心思路是先统计每个阵营的人数，然后根据题设条件做出最优选择。

1. 统计各阵营人数

我们可以使用一个哈希表（在C++中是 std::map 或 std::unordered_map）来存储每个阵营编号及其对应的人数。我们遍历输入的 $n$ 个阵营编号，并更新哈希表中每个阵营的人数。

2. 确定初始票数和最大额外票数

在统计完所有阵营的人数后，我们可以进行以下计算：

小明的初始票数：直接从哈希表中查询键为 $m$ 的值，这就是小明自己阵营的票数。
可争取到的最大额外票数：我们需要找到除小明阵营 $m$ 外，人数最多的那个阵营。我们可以遍历哈希表，维护一个变量 max_other_votes，记录所有非 $m$ 阵营中的最大人数。

3. 处理特殊情况并计算总票数

首先判断是否所有人都属于小明的阵营。这可以通过比较小明的初始票数和总人数 $n$ 来实现。如果两者相等，说明无需游说，最终票数就是 $n$ 。
否则，最终的最大票数就是 小明的初始票数 + 可争取到的最大额外票数。

这个过程确保了我们能正确处理所有情况并找到最优解。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    map<int, int> camp_counts;
    for (int i = 0; i < n; ++i) {
        int camp_id;
        cin >> camp_id;
        camp_counts[camp_id]++;
    }

    int my_votes = 0;
    if (camp_counts.count(m)) {
        my_votes = camp_counts[m];
    }

    if (my_votes == n) {
        cout << n << endl;
        return 0;
    }

    int max_other_votes = 0;
    for (auto const& [camp_id, count] : camp_counts) {
        if (camp_id != m) {
            max_other_votes = max(max_other_votes, count);
        }
    }

    cout << my_votes + max_other_votes << endl;

    return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Map<Integer, Integer> campCounts = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int campId = sc.nextInt();
            campCounts.put(campId, campCounts.getOrDefault(campId, 0) + 1);
        }

        int myVotes = campCounts.getOrDefault(m, 0);

        if (myVotes == n) {
            System.out.println(n);
            return;
        }

        int maxOtherVotes = 0;
        for (Map.Entry<Integer, Integer> entry : campCounts.entrySet()) {
            if (entry.getKey() != m) {
                maxOtherVotes = Math.max(maxOtherVotes, entry.getValue());
            }
        }

        System.out.println(myVotes + maxOtherVotes);
    }
}

import sys
from collections import defaultdict

def main():
    try:
        line = sys.stdin.readline()
        if not line:
            return
        n, m = map(int, line.split())
        
        camps = list(map(int, sys.stdin.readline().split()))
        
        camp_counts = defaultdict(int)
        for camp_id in camps:
            camp_counts[camp_id] += 1
            
        my_votes = camp_counts[m]
        
        if my_votes == n:
            print(n)
            return
            
        max_other_votes = 0
        for camp_id, count in camp_counts.items():
            if camp_id != m:
                max_other_votes = max(max_other_votes, count)
                
        print(my_votes + max_other_votes)

    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：哈希表计数
时间复杂度：我们需要遍历一次所有 $n$ 个投票人来统计票数，时间复杂度为 $\mathcal{O}(n)$ 。之后遍历哈希表来寻找最大值，由于阵营数量最多为 $n$ ，这一步最多也是 $\mathcal{O}(n)$ 。因此，总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：需要一个哈希表来存储每个阵营的人数，最多有 $n$ 个不同的阵营。因此，空间复杂度为 $\mathcal{O}(n)$ 。