← 返回题目列表

Codeforces · 2113/D

D. 骗子

中文机器翻译题面 查看原题

您正在赌场玩新的纸牌游戏,规则如下:

  1. 游戏使用一副具有不同值的 $$$2n$$$ 卡牌。
  2. 这副牌在玩家和庄家之间平分:每人收到 $$$n$$$ 牌。
  3. 在 $$$n$$$ 轮中,玩家和庄家同时打出手中的一张顶牌。比较卡片,得分较高的卡片。获胜的牌从游戏中移除,而失败的牌则返回手牌 并放置在其他卡片之上 在玩它的玩家的手中。

注意游戏总是持续 正是 $$$n$$$ 轮。

您已跟踪洗牌情况并了解庄家手中的牌顺序(从上到下)。你想最大化你的分数,所以你可以交换手中的任意两张牌 不超过一次 (避免引起怀疑)。

确定您可以获得的最大点数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^{5}$$$) — 玩家手中的牌数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \leq a_{i} \leq 2n$$$) - 玩家手中的牌从上到下的值。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_{1}, b_{2}, \ldots, b_{n}$$$ ($$$1 \leq b_{i} \leq 2n$$$) - 庄家手中的牌从上到下的值。

保证所有卡牌的值都是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 您可以获得的最大分数。

示例

输入
复制

3
7
13 7 4 9 12 10 2
6 1 14 3 8 5 11
3
1 6 5
2 3 4
5
8 6 3 10 1
7 9 5 2 4

输出
复制

6
2
3

注意

在第一个测试用例中,卡片可以保持不变。游戏玩法将组织如下:

  1. 比较值为 $$$13$$$ 和 $$$6$$$ 的卡片。玩家获胜并获得一分。
  2. 比较值为 $$$7$$$ 和 $$$6$$$ 的卡片。玩家获胜并获得一分。
  3. 比较值为 $$$4$$$ 和 $$$6$$$ 的卡片。庄家赢了。
  4. 比较值为 $$$4$$$ 和 $$$1$$$ 的卡片。玩家获胜并获得一分。
  5. 比较值为 $$$9$$$ 和 $$$1$$$ 的卡片。玩家获胜并获得一分。
  6. 比较值为 $$$12$$$ 和 $$$1$$$ 的卡片。玩家获胜并获得一分。
  7. 比较值为 $$$10$$$ 和 $$$1$$$ 的卡片。玩家获胜并获得一分。
因此,玩家获得了 $$$6$$$ 积分。

在第二个测试用例中,价值 $$$1$$$ 和 $$$5$$$ 的牌可以交换,那么玩家的手牌看起来如下 $$$[5, 6, 1]$$$。游戏玩法将组织如下:

  1. 比较值为 $$$5$$$ 和 $$$2$$$ 的卡片。玩家获胜并获得一分。
  2. 比较值为 $$$6$$$ 和 $$$2$$$ 的卡片。玩家获胜并获得一分。
  3. 比较值为 $$$1$$$ 和 $$$2$$$ 的卡片。庄家赢了。
因此,玩家获得了 $$$2$$$ 积分。

在第三个测试用例中,价值$$$3$$$和$$$10$$$的牌可以交换,那么玩家的手牌看起来如下$$$[8,6,10,3,1]$$$。游戏玩法将组织如下:

  1. 比较值为 $$$8$$$ 和 $$$7$$$ 的卡片。玩家获胜并获得一分。
  2. 比较值为 $$$6$$$ 和 $$$7$$$ 的卡片。庄家赢了。
  3. 比较值为 $$$6$$$ 和 $$$9$$$ 的卡片。庄家赢了。
  4. 比较值为 $$$6$$$ 和 $$$5$$$ 的卡片。玩家获胜并获得一分。
  5. 比较值为 $$$10$$$ 和 $$$5$$$ 的卡片。玩家获胜并获得一分。
因此,玩家获得了 $$$3$$$ 积分。