//先补充3个函数,均在algorithm库中
//lower_bound(a.begin(), a.end(), x)返回a中大于等于x的第一个位置
//upper_bound(a.begin(), a.end(), x)返回a中大于x的第一个位置
//binary_search(a.begin(), a.end(), x)寻找a中的x若找到返回true否则返回false
/*
解题思路:虽然1e9中语言,但是n, m为1e5,n个人m场电影最多只有2 * m + n种语言
为1e5级别,所以我们需要用离散化将1e9映射到1e5
*/
时间复杂度:O((n + m)log(n + m))
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m;
int a[N], b[N], c[N];
int lang[N * 3], uni[N * 3], cntl, cntu, ans[N * 3];//lang为稀疏数组,离散化后的uni为稠密数组。
int find(int x)//find作用是把稀疏图中的语言转化为映射后稠密图所在的坐标
{
return lower_bound(uni + 1, uni + cntu + 1, x) - uni;
}
int main()
{
cin >> n;//先将出现的所有语言的种类2 * n + m读入
for (int i = 1; i <= n; i ++ )//将科学家所会的语言读入
{
scanf("%d", &a[i]);
lang[ ++ cntl] = a[i];
}
cin >> m;
for (int i = 1; i <= m; i ++ )//将科学界能听懂的语音读入
{
scanf("%d", &b[i]);
lang[ ++ cntl] = b[i];
}
for (int i = 1; i <= m; i ++ )//将科学家能看懂的字幕读入
{
scanf("%d", &c[i]);
lang[ ++ cntl] = c[i];
}
sort(lang + 1, lang + cntl + 1);//排序是为了去掉lang中的重复元素,进而转化为稠密图
//sort为时间复杂度的瓶颈
for (int i = 1; i <= cntl; i ++ )//将lang去重转化为稠密组数uni
{
if (i == 1 || lang[i] != lang[i - 1])
uni[++ cntu] = lang[i];
}
for (int i = 1; i <= n; i ++ )//记录各个科学家掌握的语言在稠密图中的位置,
ans[find(a[i])] ++ ; //可以得出哪种语言科学家掌握的最多
int ans0, ans1, ans2;//ans0为最终的答案,ans1为科学家能听懂语音的人数
ans0 = ans1 = ans2 = 0;//ans2为科学家能看懂字幕的人数
for (int i = 1; i <= m; i ++ )
{
int ansx = ans[find(b[i])], ansy = ans[find(c[i])];
//若次循环听得懂语言的科学家大于之前循环过的听得懂语言的科学家的人数
//或者听得懂语音的科学家等于之前循环过的听得懂语音的科学家的人数
//但是这次循环看的懂字母的科学家大于之前循环过的看得懂字母的科学家的人数
if (ansx > ans1 || (ansx == ans1 && ansy > ans2))
{
ans0 = i, ans1 = ansx, ans2 = ansy;
}
}
if (ans0 == 0)//说明没用科学家看得懂的语音和听的懂得字幕随便输出一个
cout << 1 << endl;
else cout << ans0 << endl;
return 0;
}
附上博客:https://blog.csdn.net/qq_61935738/article/details/125396717?spm=1001.2014.3001.5502