电影

题目 电影

思路分析

和模版题基本一致 甚至更简单

找到所有要用的语言的下标 记录在alls里面去

对alls进行排序去重

得到一个新的缩小了的数组

这个数组自然有一个新的下标

我们要用find使得原离散数组和压缩数组和操作用的数组联系起来

（find可以在压缩数组里面找到离散数组的某个值 返回一个压缩数组里的下标 利用这个下标在操作用的数组里面进行一系列操作）

科学家会的语言可能重复

那其实就是插入操作 每一个科学家就做一次对应下标内容的++

对于第i场电影 有两个属性b c

若看b 其实就是find(b) 得到的下标 看该语言会的人有多少个

如果更多就更新一下

若看c 也是同理

会b语言的更多要优先于c 因为b是很高兴 c是比较高兴

所以只有当b找到的与记录的最大值相等时 才看c

不断去更新电影号即可

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N=600010;
int a[N],b[N],c[N];
int n,m;
vector<int> alls,add;

int find(int x)
{
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(alls[mid]>=x)
            r=mid;
        else
            l=mid+1;
    }
    return r;
    // return lower_bound(alls.begin(),alls.end(),x)-alls.begin();
}

int main()
{
    cin>>n;
    while(n--){
        int a;cin>>a;
        alls.push_back(a);
        add.push_back(a);
    }
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>b[i];
        alls.push_back(b[i]);
    }
    for(int i=0;i<m;i++){
        cin>>c[i];
        alls.push_back(c[i]);
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    for(auto i:add){
        a[find(i)]++;
    }
    int res=0,Like=0,like=0;
    for(int i=0;i<m;i++){
        int L=a[find(b[i])],l=a[find(c[i])];
        if(Like<L)
            Like=L,like=l,res=i;
        else if(Like==L && like<l)
            like=l,res=i;
    }
    cout<<res+1<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 救生员 🏠 00-刷题理模型 ➡️ 离散化相关问题