【题解】CF670C Cinema

看见大佬们一个个都用map，身为蒟蒻的我瑟瑟发抖，只好手打离散化虽然时间有点慢只跑了6000ms

我这里采取的是用vector进行离散化：

vector<int>v;

v用来储存需要离散的数

read(a[i]),v.push_back(a[i]);
stable_sort(v.begin(),v.end());

读入并排序

很关键的一步操作↓↓↓

v.erase(unique(v.begin(),v.end()),v.end());

这里我来解释一下

unique()是C++标准库函数里面的函数，其功能是去除相邻的重复元素（只保留一个），所以使用前需要对数组进行排序（升序降序均可），具体使用如下：

对于长度为n数组a，unique(a+1,a+n+1)返回的是迭代器，迭代器指向的是重复元素的首地址

如果非要得到不重元素的个数，可以用 unique(a+1,a+n+1) -a - 1表示；

下面举个栗子：

比如这是去重前已排好序的数：

那么unique一遍后，就会得到如下的数组：

从这里可以看出unique只是帮你整理出不重复元素，重复的元素还是码放在后面。

所以这是我们就要用到erase：

erase是vector自带的函数,即删除a[v.begin()]~~a[v.end()-1]；

然后就可以写一个query函数找出某个数被离散化成了什么：

int query(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}

了解上述知识后就可以写出一个用vector进行离散化的模板了：

#include<bits/stdc++.h>
using namespace std;
int n,a[10005],c[10005];
//c[]即储存离散化后的数 
vector<int>v;
inline int query(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;++i) 
        scanf("%d",&a[i]),v.push_back(a[i]);
    stable_sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;++i) c[i]=query(a[i]);
}

那么关于这道题，我的思路是：

1. m部电影和n个珂学家最多有(m*2+n)种语言，我们把所有涉及的语言push到v里面，排序并进行离散化，

2. 然后开个2∗m+n的数组去统计每个人会的语言，

3. 最后枚举每个电影判断.

下面就是喜闻乐见的代码时间了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<climits>
#include<bitset>
#include<vector>
using namespace std;
#define R register int
#define LL long long
#define db double
#define I inline int
#define V inline void
const int maxn=200005;
#define F1(i,a,b) for(R i=a;i<=b;++i)
#define F2(i,a,b) for(R i=a;i>=b;--i)
#define F3(i,a,b,c) for(R i=a;i<=b;i+=c)
#define F4(i,a,b,c) for(R i=a;i>=b;i-=c)
#define min(x,y) x<y?x:y
#define max(x,y) x>y?x:y
V read(R &x)
{
    R f=1;x=0;register char c=getchar();
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    x*=f;
}
V print(R x)
{
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int a[maxn],s[maxn],n,t,index[maxn*3],m,r[maxn],maxx=-1,maxy=-1,ans=1;

//a[]表示电影语言，s[]表示电影字幕，r[]为人的语言，maxx是最多有几个人听得懂，maxy表示有几个人看得懂

//因为我害怕有没有人能听懂或看懂这样的数据，所以就把ans初值置为1
vector<int>v;
I query(R x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
int main()
{
    read(n);
    F1(i,1,n) read(r[i]),v.push_back(r[i]);
    read(m);
    F1(i,1,m) read(a[i]),v.push_back(a[i]);
    F1(i,1,m) read(s[i]),v.push_back(s[i]);
    stable_sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    F1(i,1,n) t=query(r[i]),++index[t];
    F1(i,1,m)
    {
        R x=query(a[i]),y=query(s[i]);
        if(index[x]>maxx)
            maxx=index[x],maxy=index[y],ans=i;
        //如果两部电影能听懂的人一样多，就比较能看懂字幕的人的多少
        else if(index[x]==maxx&&index[y]>maxy)
            maxy=index[y],ans=i;
    }
    print(ans);
    return 0;
}