Cinema （CodeForces - 670C ，离散化入门）

一.题目链接：

CodeForces-670C

二.题目大意：

有 n 个人，每人会且仅会一种语言.  （n ≤ 2e5）

语言有各自的编号（≤ 1e9）

这些人去看电影，一共有 m 种电影. （m ≤ 2e5）

每个电影的声音与字幕语言都不一样.

若有人的语言与声音语言一样，则称这个人很高兴♂.

若有人的语言与字幕语言一样，则称这个人比较高兴.

现让你选择一场电影，使得此电影中，很高兴的人最多，在此条件下，再使比较高兴的人最多.

三.分析：

因为要统计每种语言的人数，而语言编号 ≤ 1e9，存不下.

所以考虑离散化.

可得离散化之后，语言总数最多 n + 2m 种.

详见代码.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)2e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;

int a[M + 5];
int b[M + 5];
int c[M + 5];
int lan[3 * M + 5];
int num[3 * M + 5];

int tofind(int x, int len)
{
    return lower_bound(lan + 1, lan + len + 1, x) - lan;
}

int discrete(int n, int m)
{
    int len = 0;
    for(int i = 1; i <= n; ++i)
        lan[++len] = a[i];
    for(int i = 1; i <= m; ++i)
    {
        lan[++len] = b[i];
        lan[++len] = c[i];
    }
    sort(lan + 1, lan + len + 1);
    return unique(lan + 1, lan + len + 1) - (lan + 1);
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int m;
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i)
        scanf("%d", &b[i]);
    for(int i = 1; i <= m; ++i)
        scanf("%d", &c[i]);
    int len = discrete(n, m);
    for(int i = 1; i <= n; ++i)
        num[tofind(a[i], len)]++;
    int ans = 1;
    int num1Max = 0;
    int num2Max = 0;
    for(int i = 1; i <= m; ++i)
    {
        int num1 = num[tofind(b[i], len)];
        int num2 = num[tofind(c[i], len)];
        if(num1 > num1Max || num1 == num1Max && num2 > num2Max)
        {
            ans = i;
            num1Max = num1;
            num2Max = num2;
        }
    }
    printf("%d\n", ans);
    return 0;
}