A81915.我要成为出题者!

普及-

官方

通过率:0%

时间限制:3.00s

内存限制:256MB

题目描述

一个比赛包含 nn 道题目,要求第 ii 道题目的难度预计不超过 bib_i

现在已经有 nn 个备选题目,第 ii 个备选题目的难度为 aia_i。最初,a1,a2,,ana_1, a_2, \ldots, a_nb1,b2,,bnb_1, b_2, \ldots, b_n 都是按从小到大的顺序排列的。

在决定比赛题目时,你必须从备选题目中选择,但是你可以新出一道任意难度的题目加入到备选题目中,并把此时备选题目中最难的那道题删除。

找到使 aibia_i \le b_i 对所有 ii 成立所需提出的最少新题目数量。

输入格式

第一行包含一个正整数,表示题目的数量。

第二行包含长度为 nn 的数组 aa

第三行包含长度为 nn 的数组 bb

输出格式

输出一个整数,表示最少需要提出的题目的数量。

输入输出样例

  • 输入#1

    6
    1000 1400 2000 2000 2200 2700
    800 1200 1500 1800 2200 3000
    

    输出#1

    2
    
  • 输入#2

    6
    4 5 6 7 8 9
    1 2 3 4 5 6

    输出#2

    3

说明/提示

在第一个样例中:

  • 提出一道难度为 w=800w=800 的题目,aa 变为 [800,1000,1400,2000,2000,2200][800,1000,1400,2000,2000,2200]
  • 提出一道难度为 w=1800w=1800 的题目,aa 变为 [800,1000,1400,1800,2000,2000][800,1000,1400,1800,2000,2000]

可以证明,通过提出更少的新题目是无法达到目标的。

在第二个样例中:

  • 提出一道难度为 w=1w=1 的题目,aa 变为 [1,4,5,6,7,8][1,4,5,6,7,8]
  • 提出一道难度为 w=2w=2 的题目,aa 变为 [1,2,4,5,6,7][1,2,4,5,6,7]
  • 提出一道难度为 w=3w=3 的题目,aa 变为 [1,2,3,4,5,6][1,2,3,4,5,6]

可以证明,通过提出更少的新题目是无法达到目标的。

部分分设置:

测试点编号 nn \leq aia_i\leq 特殊性质
141 \sim 4 100100 10310^3
565 \sim 6 10610^6 10810^8 初始的备选题难度都符合条件
7107 \sim 10 10610^6 10810^8
首页