AcWing 103. 电影--离散化的应用

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 103. 电影--离散化的应用原题链接简单

作者：

well188 , 2020-10-15 20:04:40 , 所有人可见 , 阅读 7198

62

19

数据离散化

定义：把无穷大集合中的若干个元素映射为有限集合以便于统计的方法。
当数据之间差值很大，即使排完序后，两个数之间仍有很大的差值，不适合直接用下标表示，这样会导致数组开的过大，容量不够，且中间有很多空没有用。针对这种情况，就想到把这间距很大的 m 个数据，在映射到 [1-m] 上，这样就会有效的减少数组的大小，且中间不会有浪费的空间。
即把稀疏的数据变的稠密起来。

步骤

1、用 lang 数组收集所有语言。
2、对 lang 数组排序、去重后保存到 uni 语言，uni 也就是语言的稠密编号。
3、find 函数用于把原始的稀疏编号转变为稠密编号。
4、ans 数组记录每种语言的科学家数。即这门语言有多少科学家会。
5、遍历所有电影，以每部电影的语音语言为条件，在ans数组中找最大值，若有多个相同的最大值，就找字幕语言最多的。

代码片段

1.原始编号的范围是 $1-10^9$ ，数据范围过大，超出数组可以保存的最大范围，但观察到这么大的范围其实只使用了很少的一部分（ $10^5$ 级别），故用 uni 数组存储稠密化的语言编号。
这时，需要一个find函数，完成从稀疏编号到稠密编号的转化。

//使用库函数
    int find(int x){
        return lower_bound(uni+1,uni+1+k,x)-uni;
    }

//也可以直接二分
    int find(int x){
        int l=1,r=k+1;
        while(l<r){
            int mid=(l+r)/2;
            if(uni[mid]>=x) r=mid;
            else l=mid+1;
        }
        return r;
    }

2.统计 uni 数组中，每种语言有多少个科学家会说，并用 ans 数组记录。
a 数组存的是原始的稀疏编号，这是遍历所有科学家，得到的每个科学家会说的语言。
ans 数组存的是稠密编号，变成稠密编号主要是便于存储和便于遍历所有语言，否则过完一个语言，下个语言不知道哪里去找（每个语言的原始编号并不是连续的）。
所以，把 a 数组的稀疏编号拿到 find 函数里面过一下，就变成 ans 数组需要的稠密编号。
3.如果出现当所有的电影的声音和字幕语言，所有的科学家都不懂的极端情况，随便选一个（以前没有数据加强后出现这个极端数据）。

    for(int i=1;i<=n;i++) ans[find(a[i])]++;

完整代码

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,k=0,tot=0;
const int N=2e5+50;
//3*N是因为语言的来源有3个地方，假设都不相同，则有3*N种语言
int lang[3*N],uni[3*N],a[N],b[N],c[N],ans[3*N];
//find作用是把稀疏编号转为稠密编号
int find(int x){
    return lower_bound(uni+1,uni+1+k,x)-uni;
}

int main(){
    //保存科学家会的语言，并用lang记录
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        lang[++tot]=a[i];
    }
    //保存电影音频的语言，并用lang记录
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&b[i]);
        lang[++tot]=b[i];
    }
    //保存电影字幕的语言，并用lang记录
    for(int i=1;i<=m;i++){
        scanf("%d",&c[i]);
        lang[++tot]=c[i];
    }
    //排序lang，为了去重复
    sort(lang+1,lang+1+tot);
    //把lang数组去重复，保存到uni数组
    //uni的数组下标做为每种语言(原有的1-10^9的稀疏编号）新的稠密编号
    for(int i=1;i<=tot;i++){
        if(i==1 || lang[i]!=lang[i-1]){
            uni[++k]=lang[i];
        }
    }
    //a[i]中保存原始的稀疏编号，用find转变成稠密编号，并用ans数组记录每种语言出现的次数。
    for(int i=1;i<=n;i++) ans[find(a[i])]++;
    //遍历所有电影，按要求找到最多科学家会的电影
    int ans0,ans1,ans2;
    //ans0保存最终结果，ans1和ans2为中间结果
    ans0=ans1=ans2=0;
    for(int i=1;i<=m;i++){
        //算出第i个电影音频语言的科学家数，和第i个字幕语言的科学家数
        int anx=ans[find(b[i])],any=ans[find(c[i])];
        //如果ans大于ans1或者前者相等且any大于ans2时，更新
        if(anx>ans1 || (anx==ans1 && any>ans2)){
            ans0=i,ans1=anx,ans2=any;
        }
    }
    //如果所有的电影的声音和字幕的语言，科学家们都不懂，随便选一个
    if(ans0==0){
        printf("%d\n",1);
    }else{
        printf("%d\n",ans0);
    }

    return 0;
}

20 评论

Xiongzx 2023-02-17 12:03

2003ms

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

const int N = 2e5 + 10;
int n;
int a[N];
int m;
pair<int, int> s[N];
unordered_map<int, int> ma;
struct like{
    int a, b, id;
}li[N];

bool cmp(like a, like b){
    if(a.a != b.a) return a.a > b.a;
    else return a.b > b.b;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){ cin >> a[i]; ma[a[i]]++;}
    cin >> m;
    for(int i = 1; i <= m; i++) cin >> s[i].fi;
    for(int i = 1; i <= m; i++) cin >> s[i].se;
    for(int i = 1; i <= m; i++){
        li[i].a = ma[s[i].fi];
        li[i].b = ma[s[i].se];
        li[i].id = i;
    }
    sort(li + 1, li + 1 + m, cmp);
    cout << li[1].id << endl;


    return 0;
}

kimihiki 2023-10-09 17:11

大佬您写的代码非常好，但我有一个疑问，我把ma换成普通数组就过不了了，为什么ma是map才能过？

kimihiki 2023-10-09 17:16

我明白了数组要开1e9会炸，但为什么map没事呢？没定义大小？用多少消耗多少内存？

Xiongzx 2023-11-16 22:15 回复了 kimihiki 的评论

map占用的内存是取决于你赋值过的空间，简单点就是说如 ma[a[i]]++; 这样的就会使得多用一个单位(如int是4byte)的内存，map主要是查询需要的时间多一点，查询到一个元素需要使用的时间是 $/mathcol O(NlogN)$ 的。具体可以上网搜索map的用法

汐_zh 5个月前

太妙了佬orz

wangyihao 2024-01-29 10:36

我怎么不过？

于木 2023-10-30 09:36

#include [HTML_REMOVED]

int n,m,k;
const int MAXN = 2e5 +50;
int a[MAXN],b[MAXN],c[MAXN];
int uni[MAXN],count[MAXN];

int query(int x){
int pos = std::lower_bound(uni+1,uni+1+k,x) - uni;
return uni[pos] == x ? pos : 0;
}

inline long long read(){
long long d = 0;signed char w = 1;/符号位最好不要用char来表示因为char可能实现是unsigned char 这时候用于表示符号机会出错不过我们可以显式的指明我们要的哪个char/
char ch = getchar();
while(ch > ‘9’ || ch < ‘0’){
if(ch == ‘-‘) w = -1;
ch = getchar();
}
while(‘0’ <= ch && ch <= ‘9’){
d = d10 + (ch^48);
ch = getchar();
}
return d*w;
}

int main(){
n =read();
for(int i = 1;i<=n;i){
a[i] = read();
uni[i] = a[i];
}
m = read();
for(int i = 1;i<=m;i) b[i] = read();
for(int i = 1;i<=m;++i) c[i] = read();

std::sort(uni+1,uni+1+n);
k = 0;
for(int i = 1;i<=n;++i){
    /*unique操作是可以在同一个数组里面进行操作的*/
    if(i == 1 || (uni[i] != uni[i-1])) uni[++k] = uni[i];
}
memset(uni+1+k,0,n-k);
for(int i = 1;i<=n;++i){
    int pos = query(a[i]);
    count[pos] += 1;
}
int ans1 = -1,ans2 =-1,ans0 =-1 ;/*这种记录性质的变量的取值一定要注意 如果这里用了0 可能就会进入if的后半段判断 这是错误的*/
for(int i = 1;i<=m;++i){
    int ansx = count[query(b[i])];
    int ansy = count[query(c[i])];
    if(ansx > ans1 || ansx == ans1 && ansy > ans2){
        ans1 = ansx; ans2 = ansy;ans0 = i;
    }
}
std::cout << ans0 << std::endl;

}

古河渚 2023-09-21 22:20

666,好题解，好久没见到离散化了

可爱抱抱呀 2022-06-16 14:43

//通过了 22/22个数据  运行时间： 5843 ms  运行空间： 67212 KB  2022年6月16日 14：41
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<n;i++){
            int a=sc.nextInt();
            map.put(a,map.getOrDefault(a,0)+1);
        }
        int m=sc.nextInt();
        int count[][]=new int[m][2];
        for(int i=0;i<m;i++){
            int b=sc.nextInt();
            count[i][0]=map.getOrDefault(b,0);
        }
        for(int i=0;i<m;i++){
            int c=sc.nextInt();
            count[i][1]=map.getOrDefault(c,0);
        }
        int ans=-1,h1=-1,h2=-1;
        for(int i=0;i<m;i++){
            if(count[i][0]>h1||count[i][0]==h1&&count[i][1]>h2){
                ans=i;
                h1=count[i][0];
                h2=count[i][1];
            }
        }
        System.out.print(ans+1);
    }
}