← 返回题目列表

Codeforces · 1972/A

A. 竞赛提案

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

一场竞赛包含 $$$n$$$ 个问题,第 $$$i$$$ 问题的难度预计最多为 $$$b_i$$$。已经有 $$$n$$$ 问题提案,第 $$$i$$$ 问题的难度为 $$$a_i$$$。最初,$$$a_1, a_2, \ldots, a_n$$$ 和 $$$b_1, b_2, \ldots, b_n$$$ 均按非降序排序。

有些问题可能比预想的更难,所以作者必须提出更多的问题。当提出难度为$$$w$$$的新问题时,将从竞赛中删除最难的问题,并按照难度非递减的方式对问题进行排序。

换句话说,在每个操作中,您选择一个整数$$$w$$$,将其插入数组$$$a$$$中,以非降序对数组$$$a$$$进行排序,并从中删除最后一个元素。

找出对所有 $$$i$$$ 产生 $$$a_i\le b_i$$$ 的新问题的最少数量。

输入

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

每个测试用例的第一行只包含一个正整数$$$n$$$ ($$$1 \leq n \leq 100$$$),代表问题的数量。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的数组 $$$a$$$ ($$$1\le a_1\le a_2\le\cdots\le a_n\le 10^9$$$)。

每个测试用例的第三行包含一个长度为 $$$n$$$ 的数组 $$$b$$$ ($$$1\le b_1\le b_2\le\cdots\le b_n\le 10^9$$$)。

输出

对于每个测试用例,在新行中打印一个整数作为答案。

示例

输入 #1

2
6
1000 1400 2000 2000 2200 2700
800 1200 1500 1800 2200 3000
6
4 5 6 7 8 9
1 2 3 4 5 6

输出 #1

2
3

注意

在第一个测试用例中:

- 提出一个难度为 $$$w=800$$$ 的问题,并且 $$$a$$$ 变为 $$$[800,1000,1400,2000,2000,2200]$$$。
- 提出一个难度 $$$w=1800$$$ 的问题,并且 $$$a$$$ 变为 $$$[800,1000,1400,1800,2000,2000]$$$。

可以证明,提出较少的新问题是不可能达到目标的。

在第二个测试用例中:

- 提出一个难度 $$$w=1$$$ 的问题,并且 $$$a$$$ 变为 $$$[1,4,5,6,7,8]$$$。
- 提出一个难度为 $$$w=2$$$ 的问题,并且 $$$a$$$ 变为 $$$[1,2,4,5,6,7]$$$。
- 提出一个难度为 $$$w=3$$$ 的问题,并且 $$$a$$$ 变为 $$$[1,2,3,4,5,6]$$$。

可以证明,提出较少的新问题是不可能达到目标的。