AcWing 103. 电影（map、pair连用or离散化）
题目
方法一（map+pair）
其实上面这么长巴拉巴拉就是在说
首先，每个科学家会的语言都不同。但是呢每部电影的字幕和语言是不一样的（字幕和语言一定不相同）
要求找到一部电影使得在场能听懂的科学家最多（如果存在两部及以上的电影的语言听懂人数相同的话，再去查找更多能看懂字幕的那部电影）
思路分析
1、使用map容器来存储科学家们听的懂的语言。
2、使用pair（或者结构体）来存储科学家们能听得懂的语言和看的懂的字幕。
3、然后先查找哪部电影最多科学家能听懂。
4、接着再判断是否需要再查找哪部电影最多科学家能够看懂。
ACcode
#include<iostream>
#include<cstring>
#include<algorithm>
#include<utility>
#include<map>
using namespace std;const int maxn = 200010;#define c_a first //记录第i部电影的语音采用的编号
#define c_b second //记录第i部电影的字幕采用的编号
#define pii pair<int, int> //存储某部电影所采用的语音编号和字幕编号map<int, int>c; //记录科学家听得懂的某种语言出现的次数
pii p[maxn];int a[maxn]; //记录第i个科学家懂得的语言int main() {int n, m;std::ios::sync_with_stdio(false); //消除输入输出缓存std::cin.tie(0); //解除cin与cout的绑定，加快速率。cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];c[a[i]]++;}cin >> m;for (int i = 0; i < m; i++) {cin >> p[i].c_a;}for (int i = 0; i < m; i++) {cin >> p[i].c_b;}//优先选择听懂电影语音的int max_a = 0, idx = 0;//max_a表示听得懂的语言最多的数目//idx用于记录电影编号for (int i = 0; i < m; i++) {if (max_a < c[p[i].c_a]) {max_a = c[p[i].c_a];idx = i;}}int max_b = 0;//max_b表示看得懂字幕最多的数目for (int i = 0; i < m; i++) {if (max_a == c[p[i].c_a]) {if (max_b < c[p[i].c_b]) {max_b = c[p[i].c_b];idx = i;}}}cout << idx + 1; //因为上述程序是由0开始遍历，故加1return 0;
}方法二 （离散化）
来源于AcWing大佬的想法 大佬解题思路加源代码
思路分析
1、将不通序列中的所有可能都映射到一个数组中。
2、然后利用该数组进行排序和去重。
3、再然后再利用一些二分查找去计数就欧了。
ACcode
#include<iostream>
#include<algorithm>
using namespace std;const int maxn = 200010;
int lang[3 * maxn], uni[3 * maxn];
int a[maxn], b[maxn], c[maxn];
int ans[3 * maxn];int idx = 0, tot = 0;//find作用是把稀疏编号转为稠密编号
int find(int x) {return lower_bound(uni + 1, uni + 1 + idx, x) - uni;
}
int main() {int n, m;cin >> n;for (int i = 1; i <= n; i++) { //科学家会的语言cin >> a[i];lang[++tot] = a[i];}cin >> m;for (int i = 1; i <= m; i++) { //电影音频的语言cin >> b[i];lang[++tot] = b[i];}for (int i = 1; i <= m; i++) { //电影字幕的语言cin >> c[i];lang[++tot] = c[i];}//排序lang，为了后续中的去重复操作sort(lang + 1, lang + 1 + tot);//把lang数组去重复，保存到uni数组for (int i = 1; i <= tot; i++) {if (i == 1 || lang[i] != lang[i - 1]) {uni[++idx] = lang[i];}}//用find转变成稠密编号，并用ans数组记录每种语言出现的次数。for (int i = 1; i <= n; i++) ans[find(a[i])]++;//遍历所有电影，按要求找到最多科学家会的电影int ans0, ans1, ans2;//ans0保存最终结果，ans1和ans2为中间结果ans0 = ans1 = ans2 = 0;for (int i = 1; i <= m; i++) {//算出第i个电影音频语言的科学家数，和第i个字幕语言的科学家数int anx = ans[find(b[i])], any = ans[find(c[i])];//如果ans大于ans1或者前者相等且any大于ans2时，更新if (anx > ans1 || (anx == ans1 && any > ans2)) {ans0 = i, ans1 = anx, ans2 = any;}}//如果所有的电影的声音和字幕的语言，科学家们都不懂，随便选一个if (ans0 == 0) {printf("%d\n", 1);}else {printf("%d\n", ans0);}return 0;
}