离散化 cinema CF670C
莫斯科在举办一场重要的有 $n$ 个不同国家的珂学家参与的国际会议,每个珂学家都只会一种语言。为了方便起见,我们规定一种语言用 $1$ 到 $10^9$ 的数来描述。
在会议之后的晚上,珂学家们决定去看电影。他们去的电影院有 $m$ 场电影,每场有两个不同的数字,分别代表配音的语言和字幕的语言。
如果一个珂学家能听懂配音,他会非常愉悦;如果能看懂字幕,他会比较满意。
如果既看不懂也听不懂,他会很生气。 珂学家们决定去看同一场电影,你必须帮助他们选择一场电影,让愉悦的人最多的前提下,比较满意的人最多。
输入格式:
第一行一个整数 $n(1≤n≤200000)$ 表示珂学家个数。
第二行n个整数 $a_1, a_2, ..., a_n(1 \leq a_i \leq 10^9)$ 表示珂学家们会的语言。
第三行一个整数 $1≤m≤200000$ 表示电影的场数。
第四行m个整数 $b_1,b_2,...,b_n(1 \leq b_j \leq 10^9)$ 表示电影的配音用的语言。 第五行 $m$ 个整数 $c_1,c_2,...,c_n(1 \leq c_j \leq 10^9)c$ 表示电影的字幕用的语言。
输出格式:
一个整数表示安排哪一场电影。 如果有多种情况,选择比较满意的方案输出。
解题思路
由于数据范围过大,一次性统计个数肯定会爆,而珂学家的个数只有2e5个,所以我们可以想到用离散化做。
离散化的目标:在大小关系不变的情况下,将数值范围压缩。
离散化的过程:先排序(这里改变了顺序),然后压缩,最后还原顺序。
例如将1 8 3 20004131 213513离散化:
1.排序:1 3 8 213513 20004131
2.压缩:1 2 3 4 5
3.还原:1 3 2 5 4
核心代码:
void discrete(){
tmp=0;
for(int i=1;i<=n;i++){
mem[i]=a[i];//用于保存原来的顺序
}
sort(a+1,a+n+1);//排序
//压缩
for(int i=1;i<=n;i++){
if(i==1||a[i]!=a[i-1]){
b[++tmp]=a[i];
}
}
return ;
}
void solve(){//还原
for(int i=1;i<=n;i++){
ans[i]=lower_bound(b+1,b+tmp+1,mem[i])-b;
}
}
代码
#include<bits/stdc++.h>
using namespace std;
int lang[600005];
int a[600005];
int n,m;
int b[600005];
int lc[600005];
int ac[600005];
int accept[200005],like[200005];
int tmp;
int mem[600005];
//将所有语言都归并起来并且压缩
void discrete(){
sort(lang+1,lang+n+2*m+1);
for(int i=1;i<=n+2*m;i++){
if(i==1||lang[i]!=lang[i-1]){
b[++tmp]=lang[i];
}
}
return ;
}
//还原并且统计每个语言会的人数
void solve(){
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+tmp+1,mem[i])-b;
lc[a[i]]++;
ac[a[i]]++;
}
for(int i=1;i<=m;i++){//还原较为满意与非常愉悦的语言
like[i]=lower_bound(b+1,b+tmp+1,like[i])-b;
accept[i]=lower_bound(b+1,b+tmp+1,accept[i])-b;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>lang[i];
mem[i]=lang[i];
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>like[i];
lang[i+n]=like[i];
}
for(int i=1;i<=m;i++){
cin>>accept[i];
lang[i+m+n]=accept[i];
}
discrete();
solve();
int Max=0,Maxn=1,Maxa=0;
for(int i=1;i<=m;i++){
if(lc[like[i]]>Max){
Max=lc[like[i]];
Maxn=i;
Maxa=ac[accept[i]];
}else if(lc[like[i]]==Max){
if(ac[accept[i]]>Maxa){
Maxn=i;
Maxa=ac[accept[i]];
}
}
}
cout<<Maxn;
return 0;
}
本文链接:https://kaispace.com.cn/index.php/archives/467/
如果未注明出处,复制公开后需将注明本博客链接。打赏作者