// AcWing 103

#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;
#define _for(i, a, b) for (int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)

// 排序并离散化， 语言种类在1e9的级别，但是科学家数目和电影数目给在2e5级别
// 我们通过离散化数组可以达成将复杂度降低成和数组大小有关的级别。
struct movie {
    int num;
    int first, second;
    int fans, sans;
};

const int N = 2e5 + 10;
int a[3 * N];
int b[3 * N];
int c[3 * N];
int ans[3 * N];
movie mv[3 * N];
unordered_map<int, int> umap;
int n, m, aindex, bindex;

bool cmpmovie(movie m1, movie m2) {
    if (m1.fans == m2.fans) return m1.sans > m2.sans;
    return m1.fans > m2.fans;
}

int query(int x) { return lower_bound(b, b + bindex, x) - b; }

int main() {
    scanf("%d", &n);
    _for(i, 0, n) { scanf("%d", &a[aindex++]); }
    scanf("%d", &m);
    _for(i, 0, m) {
        scanf("%d", &mv[i].first);
        a[aindex++] = mv[i].first;
        mv[i].num = i + 1;
    }
    _for(i, 0, m) {
        scanf("%d", &mv[i].second);
        a[aindex++] = mv[i].second;
    }
    _for(i, 0, n) c[i] = a[i];
    sort(a, a + aindex);
    _for(i, 0, aindex) {
        if (i == 0 || a[i] != a[i - 1]) {
            b[bindex++] = a[i];
        }
    }
    _for(i, 0, n) { ans[query(c[i])]++; }
    _for(i, 0, m) {
        mv[i].fans = ans[query(mv[i].first)];
        mv[i].sans = ans[query(mv[i].second)];
    }
    sort(mv, mv + m, cmpmovie);
    cout << mv[0].num << endl;
    return 0;
}

离散化

离散化适合在数据范围很大但是又只使用部分数据的时候使用

例题 ： AcWing 103

离散化函数：

sort(a, a + n);
for(int i = 0; i < n; i ++ ) {
    if(i == 0 || a[i] != a[i-1]) {
        b[m++] = a[i];
    }
}
//排序后进行离散化
int query (int x) {
    return low_bound(b, b + m, x) - b;
}
//查找数据映射到哪个整数上了

离散化概念：

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：

原数据：1,999,100000,15；处理后：1,3,4,2；

原数据：{100,200}，{20,50000}，{1,400}；

处理后：{3,4}，{2,6}，{1,5}；

​ — 来自 《百度百科》

简单的来说就是一个把元素映射的过程，以减小数据范围，方便进行计算。

常用在不关注数据本身的题目

小技巧：

//简便的for循环
#define _for(i, a, b) for(int i = (a); i < (b); i ++ )
#define _rep(i, a, b) for(int i = (a); i <= (b); i ++ )

//sort的cmp函数
struct movie {
    int first, second;
}
bool cmp(movie m1, movoie m2) {
    if(m1.first == m2.first) return m1.second > m2.second;
    return m1.first > m2.first;
}