当前位置:首页 > 数学 > 正文
CF1637E Best Pair
180+

题目大意:n个数,取出两个不同的数字,价值为两数之和乘以两数出现次数之和,求最大价值。另外,有m个搭配是不允许的!

题意翻译

给定一个长度为 $n$ 的数组 $a$。给出如下定义:

– 定义 $cnt_x$ 为 $x$ 在数组 $a$ 中出现的次数,
– 定义 $f(x,y)=(cnt_x+cnt_y)\cdot(x+y)$。

同时,给定由 $2m$ 个数对 $(x_1,y_1),(y_1,x_1),(x_2,y_2),(y_2,x_2),\cdots,(x_m,y_m),(y_m,x_m)$ 组成的集合 $S$。

你需要计算出 $\max f(u,v)$,要求 $u,v$ 都出现在数组中,$u\neq v$,且 $(u,v)$ 不在集合 $S$ 中。

数据范围:

– $t$ 组数据,$1\leqslant t\leqslant 10^4$。
– $2\leqslant n,\sum n\leqslant 3\times 10^5$,$0\leqslant m,\sum m\leqslant 3\times 10^5$。
– $1\leqslant a_i\leqslant 10^9$,$1\leqslant x_i<y_i\leqslant 10^9$。

Translated by Eason_AC

题目描述

You are given an array $ a $ of length $ n $ . Let $ cnt_x $ be the number of elements from the array which are equal to $ x $ . Let’s also define $ f(x, y) $ as $ (cnt_x + cnt_y) \cdot (x + y) $ .

Also you are given $ m $ bad pairs $ (x_i, y_i) $ . Note that if $ (x, y) $ is a bad pair, then $ (y, x) $ is also bad.

Your task is to find the maximum value of $ f(u, v) $ over all pairs $ (u, v) $ , such that $ u \neq v $ , that this pair is not bad, and also that $ u $ and $ v $ each occur in the array $ a $ . It is guaranteed that such a pair exists.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10\,000 $ ) — the number of test cases.

The first line of each test case contains two integers $ n $ and $ m $ ( $ 2 \le n \le 3 \cdot 10^5 $ , $ 0 \le m \le 3 \cdot 10^5 $ ) — the length of the array and the number of bad pairs.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — elements of the array.

The $ i $ -th of the next $ m $ lines contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i < y_i \le 10^9 $ ), which represent a bad pair. It is guaranteed that no bad pair occurs twice in the input. It is also guaranteed that $ cnt_{x_i} > 0 $ and $ cnt_{y_i} > 0 $ .

It is guaranteed that for each test case there is a pair of integers $ (u, v) $ , $ u \ne v $ , that is not bad, and such that both of these numbers occur in $ a $ .

It is guaranteed that the total sum of $ n $ and the total sum of $ m $ don’t exceed $ 3 \cdot 10^5 $ .

输出格式

For each test case print a single integer — the answer to the problem.

输入输出样例

输入样例 #1

3
6 1
6 3 6 7 3 3
3 6
2 0
3 4
7 4
1 2 2 3 1 5 1
1 5
3 5
1 3
2 5

输出样例 #1

40
14
15

说明

In the first test case $ 3 $ , $ 6 $ , $ 7 $ occur in the array.

– $ f(3, 6) = (cnt_3 + cnt_6) \cdot (3 + 6) = (3 + 2) \cdot (3 + 6) = 45 $ . But $ (3, 6) $ is bad so we ignore it.
– $ f(3, 7) = (cnt_3 + cnt_7) \cdot (3 + 7) = (3 + 1) \cdot (3 + 7) = 40 $ .
– $ f(6, 7) = (cnt_6 + cnt_7) \cdot (6 + 7) = (2 + 1) \cdot (6 + 7) = 39 $ .

The answer to the problem is $ \max(40, 39) = 40 $ .

解题思路

首先,数字有重复,我们可以先去重,并统计每个数字出现的次数。

接着,用哈希表记录不合法情况。

最后,想办法解决其他问题。

不难想到暴力方法:枚举第一个数和第二个数,暴力计算最优值。

枚举的优化:改变枚举对象,数字种类至多n个,但出现次数约根号种。如果已知第一个数字和第二个数字的次数,那么只需要选择该次数中数值最大的即可。

现在问题是,有m个搭配是不合法的,最大值可能不合法,此时我们只能继续往下找。由于不合法情况共m种,所以往下走的次数至多m次,并不影响时间复杂度$O(n\sqrt{n})$。

优化:因为还需要套哈希表、map等数据结构,所以容易超时。我们还可以去重,枚举a和b跟b和a是等价的,如果我们枚举的是出现次数多的数字,那么另一个数字的出现次数不大于第一个数字的出现次数,从而实现O(n)枚举,因为次数之和为n。

排序可以使用索引排序,vector等,因为排序带log,所以就不手写哈希表了,模数取不好还可能被卡呢!

程序实现

CF1637E Best Pair:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!