AcWing 103. 电影(离散化)
原题链接
简单
作者:
Value
,
2020-09-07 10:27:19
,
所有人可见
,
阅读 457
可算会了!
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2 * 1E5 + 10;
vector<int> languages;
struct node{
int id;
int say, word;
int happy;
int fit;
}film[N];
int find(int x){
int l = 0, r = languages.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(languages[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
bool cmp(node a, node b){
if(a.happy != b.happy) return a.happy > b.happy;
return a.fit > b.fit;
}
int main(){
int n; cin >> n;
for(int i = 0; i < n; i ++ ){
int tmp; scanf("%d", &tmp);
languages.push_back(tmp);
}
sort(languages.begin(), languages.end());
cin >> n;
for(int i = 0; i < n; i ++ ){
film[i].id = i + 1;
int say; scanf("%d", &say);
film[i].say = say;
int x = find(say);
if(languages[x] != say) film[i].happy = 0;
else{
int cnt = 0;
for(int i = x; i < languages.size(); i ++ ){
if(languages[i] == say) cnt ++ ;
else break;
}
film[i].happy = cnt;
}
}
for(int i = 0; i < n; i ++ ){
int word; scanf("%d", &word);
film[i].word = word;
int x = find(word);
if(languages[x] != word) film[i].fit = 0;
else{
int cnt = 0;
for(int i = x; i < languages.size(); i ++ ){
if(languages[i] == word) cnt ++ ;
else break;
}
film[i].fit = cnt;
}
}
sort(film, film + n, cmp);
cout << film[0].id << endl;
return 0;
}