CF670C Cinema

题解 算法-排序 普及+/提高
题目链接 编辑文章

题意

从 $m$ 部电影中选出 $1$ 部给 $n$ 个人看。每部电影的配音和字幕都使用的不同的语言,每个人只掌握一种语言,用 $1\le id\le 10^{9}$ 的数表示不同语言。

对于选出来的电影,如果某人能听懂配音,他会非常高兴;如果能看懂字幕,他会比较高兴。问:选择哪部电影,使得非常高兴的人最多;如果一样多,应使比较高兴的人最多。

$n,m\le 200000$ 。

题解

显然可以对每部电影分别计算出两个属性,最后取最大即可。

不同的人掌握的语言可能相同,那么可以把相同语言的人合并,记录语言和人数在数组 $\text{s[]}$ 中。

然后将两个属性分开考虑,先考虑配音。将配音的语言和所有人掌握的语言从小到大排序,可以在 $O(n+m)$ 下很容易的得到非常高兴的人的个数。字幕同理。

具体的实现是对电影的两个属性,用结构体 $(id,lan,ans)$ 表示电影的序号语言非常高兴/较高兴的人数。对于观众,我懒得再开结构体,用 $(id,lan)$ 表示语言人数

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,m,a[200005];
struct node {
    int id,lan,ans;
} b[200005],c[200005],s[200005];

inline bool cmp(node x,node y) { return x.lan<y.lan; } //按语言排序

inline bool cmp2(node x,node y) { return x.id<y.id; } //按序号排序,方便统计答案

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1);
    int cnt=1;
    s[1].id=a[1]; s[1].lan=1;
    for (int i=2;i<=n;i++)
    {
        if (a[i]==a[i-1]) s[cnt].lan++;
        else s[++cnt].id=a[i],s[cnt].lan=1;
    } //合并相同语言的人
    n=cnt;
    m=read();
    for (int i=1;i<=m;i++) b[i].lan=read(),b[i].id=i;
    for (int i=1;i<=m;i++) c[i].lan=read(),c[i].id=i;
    sort(b+1,b+m+1,cmp);
    sort(c+1,c+m+1,cmp);
    int j=1;
    for (int i=1;i<=m;i++) //处理配音
    {
        while (s[j].id<b[i].lan) j++;
        if (s[j].id==b[i].lan) b[i].ans+=s[j].lan;
    }
    j=1;
    for (int i=1;i<=m;i++) //处理字幕
    {
        while (s[j].id<c[i].lan) j++;
        if (s[j].id==c[i].lan) c[i].ans+=s[j].lan;
    }
    sort(b+1,b+m+1,cmp2);
    sort(c+1,c+m+1,cmp2); //按序号还原原来的顺序
    int ans=1;
    for (int i=2;i<=m;i++)
    {
        if (b[i].ans<b[ans].ans) continue;
        if (b[i].ans>b[ans].ans) ans=i; //非常高兴的人较多
        else if (c[i].ans>c[ans].ans) ans=i; //非常高兴的人相同,较高兴的人较多
    }
    return !printf("%d",ans);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空