A105170.赛题挑选
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
在一次编程比赛中,比赛组委会需要从一系列备选题目中筛选出合适的题目,这些题目将作为比赛的正式题目。每道题目都有一个难度值,同时每个参赛者在比赛前都会收到一份题目难度预期列表,要求每道题目的难度不超过该预期。
组委会的任务是,从备选题目中选择合适的题目,或者添加新的题目来确保比赛题目的难度不会超过参赛者的预期,且题目的难度符合一定要求。新题目的难度可以根据需要自由设定,组委会需要尽量减少新题目的数量。
输入格式
第一行输入一个整数 n,表示备选题目的数量。
第二行输入一个长度为 n 的数组 a,表示备选题目的难度。
第三行输入一个长度为 n 的数组 b,表示参赛者的题目难度预期。
输出格式
输出一个整数,表示最少需要提出的题目数量。
输入输出样例
输入#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=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]。
- 可以证明,通过提出更少的新题目是无法达到目标的。
数据范围:
10≤M≤2×106