A105170.赛题挑选

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

在一次编程比赛中,比赛组委会需要从一系列备选题目中筛选出合适的题目,这些题目将作为比赛的正式题目。每道题目都有一个难度值,同时每个参赛者在比赛前都会收到一份题目难度预期列表,要求每道题目的难度不超过该预期。

组委会的任务是,从备选题目中选择合适的题目,或者添加新的题目来确保比赛题目的难度不会超过参赛者的预期,且题目的难度符合一定要求。新题目的难度可以根据需要自由设定,组委会需要尽量减少新题目的数量。

输入格式

第一行输入一个整数 nn,表示备选题目的数量。
第二行输入一个长度为 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]
    • 可以证明,通过提出更少的新题目是无法达到目标的。

数据范围:

10M2×10610 \le M \le 2 \times 10^{6}

首页