Kvar_ispw17's blog
0%

CodeForces 670C Cinema 题解

Posted on Edited on In

题目链接： CodeForces 670C Cinema

第五题 Cinema 题解

Author: 第7组

2021.4.19

题目概述

有\(n\) 个人，各自会说一种语言，他们去看电影，每个电影\(q_i\)有音频语言\(a_i\)和字幕语言\(s_i\)，如果一个人能听懂，则非常开心,如果只能看懂字幕则不是非常开心但也能凑合，如果两个都不懂，他会非常愤怒。

现在要找一个电影，可以让非常开心的人最多，如果有多个方案，要求不是非常开心的最多。

题解

语言的范围是\(10^9\)，但是人数仅有\(2\times 10^5\)，于是第一步就是离散化（sort加unique）.

将语言离散化后，可以开一个数组\(e[i]\)存每个语言\(i\)有多少人会说，然后建立一个结构体存下电影的下标\(idx\)、能听懂的人数\(au\)和能看懂的人数\(su\)，然后重载小于号进行排序，分别以\(au\)和\(su\)作为第一和第二关键字即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 2e5 + 5;
const int M = 2e5 + 5;

int n, m;
int a[N], b[M], c[M];
int _a[N], tot;
int e[N];
map<int, int> t;
map<int, int> rt;

// #define DEBUG

class _data {
  public:
	int idx, au, su;
	_data() {}
	_data(int _idx, int _au, int _su) : idx(_idx), au(_au), su(_su) {}
	bool operator < (const _data &o) const {
		return au ==  o.au ? su < o.su : au < o.au;
	}
	~_data() {}
} q[M];

int main() {
#ifdef DEBUG
	freopen("C.in", "r", stdin);
#endif
	read(n);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
		_a[i] = a[i];
	}
	sort(_a + 1, _a + n + 1);
	tot = unique(_a + 1, _a + n + 1) - (_a + 1);
	// printf("tot = %d\n", tot);
	for (int i = 1; i <= tot; i++) {
		t[_a[i]] = i;
		rt[i] = _a[i];
	}
	for (int i = 1; i <= n; i++) {
		a[i] = t[a[i]];
		e[a[i]]++;
	}
	read(m);
	for (int i = 1; i <= m; i++) {
		read(b[i]);
		b[i] = t[b[i]];
	}
	for (int i = 1; i <= m; i++) {
		read(c[i]);
		c[i] = t[c[i]];
	}
	for (int i = 1; i <= m; i++) {
		q[i] = _data(i, e[b[i]], e[c[i]]);
	}
	sort(q + 1, q + m + 1);
	printf("%d\n", q[m].idx);
	return 0;
}