、值域是多少?定义域是多少
定义域是[1, 1e10^9]值域[1, 2e6]
2、我们要求的是什么?找一部让所有人观影开心最多的电影,如果存在多个答案,就选取比较开行的人最多的一部
3、如何进行离散化?
将科学家喜欢的语言编号进行离散化?因为我们求得是人数,关注得是数值本身,而不是第几个人,所以我们
可以将科学家懂得语言得编号离散在数组中
如何在离散化后的数据中处理每一部喜欢的电影人数?是否可以用二元组存储第i部电影的两个属性?<a, b>
根据第一关键字进行离散化
4、 大体思路就是二分查找+离散化
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int peo[N], movie_v[N], movie_lang[N];
int n, m;
struct M {//存储电影的三个属性,第几部,声音、字幕编号
int idx, one, two;
bool operator< (const M & a) {
return one < a.one;
}
}movie[N];
struct love {//存储每一部电影的编号、根据第一属性喜欢的人数,根据第二属性喜欢的人数
int idx, one, two;
}p[N];
bool cmp1 (const love & a1, const love & a2){
return a1.one > a2.one;
}
int find (int x) {//二分查找,寻找第一个>=x的数
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (peo[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
int main () {
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> peo[i];
cin >> m;
for (int i = 1; i <= m; i ++) cin >> movie_v[i];
for (int i = 1; i <= m; i ++) cin >> movie_lang[i];
for (int i = 1; i <= m; i ++) {
int a = movie_v[i], b = movie_lang[i];
movie[i] = {i, a, b};//将电影存储在movie结构体中
}
sort (peo + 1, peo + 1 + n);//根据表示每一个科学家喜欢的编号,不需要考虑第几个科学家,所以可以进行排序
sort (movie +1, movie + 1 + m);//根据第一属性对movie进行从大到小排序
// for (int i = 1; i <= m; i ++ ) cout << movie[i].idx << " " << movie[i].one << " " << movie[i].two << endl;
for (int t = 1; t <= m; t ++) {
int a = find (movie[t].one);
if (peo[a] != movie[t].one) a = 0;//如果不相等a就等于0
int c = a;
while (peo[a] == movie[t].one) a ++;//看后面好友没有喜欢第一属性的人
p[t].idx = movie[t].idx, p[t].one = a - c;//记录这部电影的编号、喜欢第一属性的人数
a = find(movie[t].two);
if (peo[a] != movie[t].two) a = 0;
c = a;
while (peo[a] == movie[t].two) a ++;
p[t].idx = movie[t].idx, p[t].two = a - c;//同理
}
sort (p +1, p + 1+ m, cmp1);//根据第一属性进行排序
int ans = 1;
int idx = p[1].idx;//因为第一个肯定是喜欢第一属性人数最多的电影,所以初始化为这个。
while (p[ans].one == p[ans + 1].one && ans <= m && p[ans].two < p[ans + 1].two) {//考虑喜欢第一属性人数有相等的情况,如果第二属性的人数比较大,则进行循环。一直到不满足条件
ans ++;
idx = p[ans].idx;
}
//for (int i = 1; i <= m; i ++ ) cout << p[i].idx << " " << p[i].one << " " << p[i].two << endl;
cout << idx << endl;
return 0;
}