今天做离散基础题

https://www.acwing.com/problem/content/105/

离散指的应该就是hash了

cpp
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_N = 200001; // 科学家的最大数量
const int MAX_M = 200001; // 电影的最大数量

int n, m;
int lang[MAX_N]; // 科学家懂得的语言
int voice[MAX_M], sub[MAX_M]; // 电影的语音和字幕语言
int unique_langs[MAX_N + 2 * MAX_M]; // 所有出现的语言编号
int lang_count[MAX_N + 2 * MAX_M]; // 统计每种语言有多少科学家懂得

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> lang[i];
        unique_langs[i] = lang[i];
    }

    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> voice[i];
        unique_langs[n + i] = voice[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> sub[i];
        unique_langs[n + m + i] = sub[i];
    }

    // 离散化语言编号
    sort(unique_langs, unique_langs + n + 2 * m);
    int unique_count = unique(unique_langs, unique_langs + n + 2 * m) - unique_langs;

    // 统计每种语言有多少科学家懂得
    for (int i = 0; i < n; i++) {
        int idx = lower_bound(unique_langs, unique_langs + unique_count, lang[i]) - unique_langs;
        lang_count[idx]++;
    }

    // 计算每部电影能让多少科学家开心和比较开心
    int max_happy = -1;
    int max_happy_idx = -1;
    int max_comp_happy = -1;

    for (int i = 0; i < m; i++) {
        int voice_idx = lower_bound(unique_langs, unique_langs + unique_count, voice[i]) - unique_langs;
        int sub_idx = lower_bound(unique_langs, unique_langs + unique_count, sub[i]) - unique_langs;
        int happy = lang_count[voice_idx];
        int comp_happy = lang_count[sub_idx];

        if (happy > max_happy || (happy == max_happy && comp_happy > max_comp_happy)) {
            max_happy = happy;
            max_happy_idx = i;
            max_comp_happy = comp_happy;
        }
    }

    // 输出最终选择的电影编号
    cout << max_happy_idx + 1 << endl;

    return 0;
}