看到题目可知,若每种语言a对应的人数为p[a],则最终选择的电影 i 对应最大的 p[ai] (ai表示语音),当存在多个电影放映的语音人数都最大时,选择的结果一定具有最大的 p[bi] (bi表示字幕)
总结为:所有的电影中,有一个电影i,p[ai]最大。当存在电影k满足p[ak] == p[ai]时,一定有p[ai] > p[ak] (当相等时任意选择一个即可)
原本计划利用结构体存储,并对结构体进行排序,然而时间太久,并不能实现。
再看一下题目可知,需要找的并不是排序之后的结果,而是排序后第一个值,可以直接遍历一遍记录实现
C++ 代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 200010;
// int p[N];
unordered_map<int, int> p;
struct MOVIES{
int a, b;
int index;
// void setIndex(int id)
// {
// index = id;
// }
// bool operator<(const MOVIES& mov)const{
// if(p[a] == p[mov.a])return p[b] > p[mov.b];
// return p[a] > p[mov.a];
// }
}movies[N];
int main()
{
int n; scanf("%d", &n);
for(int i = 0; i < n; ++i)
{
int x; scanf("%d", &x);
++p[x];
}
int m; scanf("%d", &m);
for(int i = 0; i < m; ++i)
{
scanf("%d", &movies[i].a);
movies[i].index = i + 1;
}
for(int i = 0; i < m; ++i)scanf("%d", &movies[i].b);
int ans = 0;
for(int i = 1; i < m; ++i)
{
if(p[movies[i].a] > p[movies[ans].a])ans = i;
else if(p[movies[i].a] == p[movies[ans].a] && p[movies[i].b] > p[movies[ans].b])ans = i;
// printf("i is %d, a is %d, b is %d, id is %d\n", i, movies[i].a, movies[i].b, movies[i].index);
}
// sort(movies, movies + m);
printf("%d\n", ans + 1);
return 0;
}
看大佬们都是利用离散化写的,发现自己用unordered_map原来是作弊了。
尝试写个离散化的
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
const int N = 200010;
//Discretization
int discre[N], bs[N], cs[N];
int cnt = 0;
int find(int a, const vector<int>& ais)
{
int l = 0, r = cnt - 1;
while(l < r)
{
int mid = (l + r)>>1;
if(ais[mid] < a)l = mid + 1;
else r = mid;
}
return r;
}
int main()
{
int n; scanf("%d", &n);
vector<int> ais(n, 0);
for(int i = 0; i < n; ++i)scanf("%d", &ais[i]);
sort(ais.begin(), ais.end());
// ais.erase(unique(ais.begin(), ais.end()), ais.end());
// int cnt = 0;
for(int i = 0; i < ais.size();)
{
int j = i;
while(j < ais.size() && ais[j] == ais[i])++j;
discre[cnt] = j - i;
ais[cnt] = ais[i];
cnt++;
i = j;
}
// for(int i = 0; i < ais.size(); ++i)
// {
// printf("a is %d, cnt is %d\n", ais[i], discre[i]);
// }
int m; scanf("%d", &m);
for(int i = 0; i < m; ++i)scanf("%d", bs+i);
for(int i = 0; i < m; ++i)scanf("%d", cs+i);
int ans = 0, ta = 0, tb = 0;
for(int i = 0; i < m; ++i)
{
int k = find(bs[i], ais);
if(bs[i] != ais[k])continue;
if(ta < discre[k])
{
ta = discre[k]; ans = i + 1;
k = find(cs[i], ais);
if(cs[i] == ais[k])tb = discre[k];
else tb = 0;
}
else if(ta == discre[k])
{
int tk = find(cs[i], ais);
if(cs[i] == ais[tk] && discre[tk] > tb)
{
tb = tk;
ans = i + 1;
}
}
// printf("i is %d, ta is %d, kv is %d, dis is %d\n", i, ta, ais[k], discre[k]);
}
printf("%d\n", ans);
return 0;
}