离散化—本人学习自用
适用场景
数的值域跨度范围很大,但数的个数很少,使用离散化只存出现的值即可
法一:使用map存储 2121ms
//思路:存下来不同语言有多少科学家懂
//把语言离散化
#include<iostream>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int N = 200000;
int n,m; //n个科学家,m个电影
map<int,int> language;
int a[N],b[N],c[N];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
language[a[i]]+=1;
}
for(auto i:language){
// printf("语言%d有%d个科学家懂\n",i.first,i.second);
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&b[i]);
}
for(int i=1;i<=m;i++){
scanf("%d",&c[i]);
}
int id=1;
int veryhappy=language[b[1]];
int happy=language[b[1]];
for(int i=2;i<=m;i++){
// printf("电影%d:有%d个科学家非常开心,有%d个科学家比较开心\n",i,language[b[i]],language[c[i]]);
if(language[b[i]]>veryhappy ||(language[b[i]]==veryhappy && language[c[i]]>happy)){
id=i;
veryhappy=language[b[i]];
happy=language[c[i]];
// printf("此时更新id为%d\n",i);
}
}
cout<<id;
return 0;
}
法二:离散化数组
两种方法区别在于稀疏数组转化为稠密数组的方法
2.1二分(效率更高)1367ms
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,k=0;
const int N=200010;
vector<int> language;
int tmp[3*N]; //保存每种语言有多少科学家会
int a[N],b[N],c[N];
//find作用是把稀疏编号转为稠密编号
int find(int x){
int l=0,r=language.size();
while(l<r){
int mid=(l+r)/2;
if(x<=language[mid]){
r=mid;
}
else l=mid+1;
}
return r;
}
int main(){
//保存科学家会的语言
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
language.push_back(a[i]);
}
//保存电影音频的语言
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&b[i]);
language.push_back(b[i]);
}
//保存电影字幕的语言
for(int i=1;i<=m;i++){
scanf("%d",&c[i]);
language.push_back(c[i]);
}
//排序并去重
sort(language.begin(),language.end());
language.erase(unique(language.begin(),language.end()),language.end());
//a[i]中保存原始的稀疏编号,用find转变成稠密编号,并用tmp数组记录每种语言出现的次数。
for(int i=1;i<=n;i++) tmp[find(a[i])]++;
int id=1;
int veryhappy=0,happy=0;
for(int i=1;i<=m;i++){
//算出第i个电影音频语言的科学家数,和第i个字幕语言的科学家数
int cur_veryhappy=tmp[find(b[i])];
int cur_happy=tmp[find(c[i])];
if(cur_veryhappy>veryhappy || (cur_veryhappy==veryhappy && cur_happy>happy)){
id=i;
veryhappy=cur_veryhappy;
happy=cur_happy;
}
}
cout<<id;
return 0;
}
2.2lower_bound 1892ms
//find作用是把稀疏编号转为稠密编号
int find(int x){
return lower_bound(language.begin(),language.end(),x)-language.begin();
}