107 人解决,165 人已尝试。
120 份提交通过,共有 689 份提交。
4.2 EMB 奖励。
单点时限: 1.0 sec
内存限制: 128 MB
HMP_Haoge 编写了一款开放世界游戏。游戏中有一个关于战斗的小游戏,首先玩家拥有 $n$ 个战士,它们的战斗力分别为 $a_1,a_2,\cdots a_n$ ;接着,玩家拥有 $n$ 个辅助,它们的辅助力分别为 $b_1,b_2,\cdots b_n$ 。
现在,玩家需要将这 $2n$ 个角色分为 $n$ 组,每组为一个战士和一个辅助,每组的战斗力为组内战士战斗力和辅助的辅助力之和。然而,开发者在开发时不小心写了一个bug,它将每个组的战斗力对 $n$ 进行了取模。形式化来说,对于第 $x$ 组,我们记该组的战斗力为 $c_x$,假设该组由第 $i$ 个战士和第 $j$ 个辅助组成,那么 $c_x = (a_i+b_j) \mod n$。
你发现了这个bug,但是你却无法改变它,这时你作为玩家,你希望完成分组,并且使得所有组的战斗力之和最大,即最大化 $\sum _{x=1}^{n}c_x$。
你只需要输出这个最大的战斗力之和即可。
首先输入一个正整数 $T$ ,表示数据组数。
对于每组数据:
第一行,一个整数 $n$ 表示战士和辅助的数目;
第二行, $n$ 个整数,第 $i$ 个数表示 $a_i$ ;
第三行, $n$ 个整数,第 $i$ 个数表示$ b_i$ ;
保证 $T$ 组测试数据的 $\sum n$ 不超过 $2\times 10^5$ 。
对于每组数据,输出一行,一个整数,表示最大的$\sum_{i=1}^nc_i$
2 4 31 45 92 65 35 89 79 32 10 1 1 4 5 1 4 1 1 4 5 1 9 1 9 8 1 0 1 9 1
8 37
【样例解释】
用二元组 $(i,j)$ 表示把 $a_i$ 和 $b_j$ 分为一组。
那么对于第一组数据,可以采用的分组方案为:$(1,3),(2,4),(3,1),(4,2)$
此时得到最大的战斗力和为:
${(31+79)\mod 4} + {(45+32)\mod 4} + {(92+35)\mod 4} + {(65+89)\mod 4} =2+1+3+2=8$
【数据范围】
$1\le T \le 2\times 10^5$
$1\le n\le 2\times 10^5,\sum n \le 2\times 10^5$,$0\le a_i,b_i \le 2\times 10^5$
107 人解决,165 人已尝试。
120 份提交通过,共有 689 份提交。
4.2 EMB 奖励。
创建: 1 年,4 月前.
修改: 1 年,4 月前.
最后提交: 7 月,2 周前.
来源: N/A