Cinema

title: Cinema
date: 2023-12-18 21:05:20
tags: 离散化
categories: 算法进阶指南

题目大意

解题思路

将 $m$ 部电影和 $n$ 个人最多涉及的 $2?m+n$ 种语言放进一个数组，排序离散化，然后用这个 $[1,2?m+n]$ 范围内大小的整数代替每一个语言，此时我们就可以用数组直接统计每一种语言的人的数量，进而循环找出符合题意的序号电影

实现代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 2e6 + 10, mod = 1e9 + 7;

int cnt[N];

int main()
{
    int n; cin >> n;
    vector<int> d;
    vector<int> a(n);
    for(int i = 0 ; i < n;  i++){
        cin >> a[i];
        d.push_back(a[i]);
    }
    
    int m; cin >> m;
    vector<int> b(m);
    for(int i = 0 ; i < m; i ++){
        cin >> b[i];
        d.push_back(b[i]);
    }
    vector<int> c(m);
    for(int i = 0; i < m; i ++){
        cin >> c[i];
        d.push_back(c[i]);
    }
    sort(d.begin(),d.end());
    d.erase(unique(d.begin(),d.end()),d.end());
    ll ans = 0;
    for(int i = 0; i < n; i ++){
        a[i] = lower_bound(d.begin(),d.end(),a[i]) - d.begin();
    }
    for(int i = 0 ; i < m; i ++){
        b[i] = lower_bound(d.begin(),d.end(),b[i]) - d.begin();
        c[i] = lower_bound(d.begin(),d.end(),c[i]) - d.begin();
    }
    
    for(int i = 0 ; i < n; i ++){
        cnt[a[i]]++;
    }
    
    int x;
    int max1 = -1,max2 = -1;
    for(int i = 0 ; i < m; i ++){
        if(max1 < cnt[b[i]]){
            max1 = cnt[b[i]];
            max2 = cnt[c[i]];
            x = i + 1;
        }
        else if(cnt[b[i]] == max1 && cnt[c[i]] > max2){
            max2 = cnt[c[i]];
            x = i + 1;
        }
    }
    cout << x;
    return 0;
}