A81915.我要成为出题者!
普及-
官方
通过率:0%
时间限制:3.00s
内存限制:256MB
题目描述
一个比赛包含 n 道题目,要求第 i 道题目的难度预计不超过 bi。
现在已经有 n 个备选题目,第 i 个备选题目的难度为 ai。最初,a1,a2,…,an 和 b1,b2,…,bn 都是按从小到大的顺序排列的。
在决定比赛题目时,你必须从备选题目中选择,但是你可以新出一道任意难度的题目加入到备选题目中,并把此时备选题目中最难的那道题删除。
找到使 ai≤bi 对所有 i 成立所需提出的最少新题目数量。
输入格式
第一行包含一个正整数,表示题目的数量。
第二行包含长度为 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]。
可以证明,通过提出更少的新题目是无法达到目标的。
部分分设置:
| 测试点编号 | n≤ | ai≤ | 特殊性质 |
|---|---|---|---|
| 1∼4 | 100 | 103 | 无 |
| 5∼6 | 106 | 108 | 初始的备选题难度都符合条件 |
| 7∼10 | 106 | 108 | 无 |