题目描述
给你 $n$ 个科学家对应的语言,$m$ 部电影的语音和字幕
让你求出最多的科学家能听懂语言的电影编号
如果有多部电影人数相同,则求最多的科学家能看懂字幕的电影编号。
参考自 @Gra大佬!
此题解只是翻译成C++语言
算法
排序 + 二分求目标区间
-
先给科学家的语言排序
-
然后遍历每部电影
优先以电影的语音为目标二分查找
得出目标的区间,就能计算区间长度,也就是会这门语言的科学家人数
然后根据人数更新答案,也就是电影编号 -
如果有多部电影能听懂语音的人数相同
就同理以电影的字幕为目标二分查找
然后更新答案 -
温馨提示:电影编号是从 $1$ 开始的!
时间复杂度
遍历电影数组,每次都二分
电影数组长度为 $M$
二分的数组是科学家的数组,则每次查找为 $log(N)$
其中 $1 \le N,M \lt 200000$
最坏情况为 $O(M*log(N)) = 200000 * log(200000) \approx 4000000$
本题时间限制为 $1s$
可以顺利通过
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
#define pii pair<int, int>
const int N = 2e5+5;
int scient[N], lang[N], sub[N];
int n, m;
pii bs(int target) {
//查找左边界
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (scient[mid] < target) l = mid + 1;
else r = mid;
}
//如果目标不存在直接返回
if (scient[l] != target) return {-1, -1};
//查找右边界
int ansL = l;
r = n - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (scient[mid] <= target) l = mid;
else r = mid - 1;
}
return {ansL, r};
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; ++i) cin >> scient[i];
cin >> m;
for (int i = 0; i < m; ++i) cin >> lang[i];
for (int i = 0; i < m; ++i) cin >> sub[i];
sort(scient, scient + n);
int ans = 0, langCnt = 0, subCnt = 0;
//遍历所有电影
for (int i = 0; i < m; ++i) {
pii bound = bs(lang[i]);//寻找当前电影的语言 在科学家语言的左右边界
if (bound.first == -1) continue;
int curLangCnt = bound.second - bound.first + 1;//通过边界可以计算有多少科学家会这个语言
//更新答案
if (curLangCnt > langCnt) {
ans = i;
langCnt = curLangCnt;
bound = bs(sub[i]);
subCnt = bound.first == -1 ? 0 : bound.second - bound.first + 1;
} else if (curLangCnt == langCnt) {
bound = bs(sub[i]);
int curSubCnt = bound.second - bound.first + 1;
if (curSubCnt > subCnt) {
ans = i;
subCnt = curSubCnt;
}
}
}
cout << ans + 1;
return 0;
}