CF1972A Contest Proposal

一场比赛包含 $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 \leq b_i$。

每个测试点包含多组测试数据。第一行包含测试用例的数量 $t$（$1 \leq t \leq 100$）。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个正整数 $n$（$1 \leq n \leq 100$），表示题目的数量。 第二行包含一个长度为 $n$ 的数组 $a$（$1 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 10^9$）。 第三行包含一个长度为 $n$ 的数组 $b$（$1 \leq b_1 \leq b_2 \leq \cdots \leq b_n \leq 10^9$）。

对于每组测试用例，输出一个整数，表示你的答案，每个答案占一行。

在第一个测试用例中： - 提出一个难度为 $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]$。 可以证明，无法通过更少的新题目达到目标。 由 ChatGPT 4.1 翻译