4729: 读书(广东省重点中学信息学邀请赛普及组)
内存限制:512 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:2
解决:0
题目描述
(广东省重点中学信息学邀请赛 (GDKOI 2024 day2普及组 第二试)
Zayin是一个热爱读书的学生。
最近,Zayin收到了一本有n个章节的书,其中每个章节i都有一个限制:她必须至少阅读了其他ai个章节,才能够获取足够的智慧来读懂该章节。
每天,Zayin都会从头到尾开始阅读这本书。对于她还不能读懂的章节(由于限制)或是已经阅读过的章节,Zayin会在那天跳过它们。
现在,Zayin想要知道至少需要多少天才能阅读完所有的n个章节。
Zayin是一个热爱读书的学生。
最近,Zayin收到了一本有n个章节的书,其中每个章节i都有一个限制:她必须至少阅读了其他ai个章节,才能够获取足够的智慧来读懂该章节。
每天,Zayin都会从头到尾开始阅读这本书。对于她还不能读懂的章节(由于限制)或是已经阅读过的章节,Zayin会在那天跳过它们。
现在,Zayin想要知道至少需要多少天才能阅读完所有的n个章节。
输入
第一行包含两个整数d, n,表示测试点编号和章节数。
第二行包含n个整数ai (0 ≤ ai<n),表示限制。
第二行包含n个整数ai (0 ≤ ai<n),表示限制。
输出
输出一行包含一个整数,表示最少需要的天数。
如果Zayin无法阅读完所有的n个章节,输出−1。
如果Zayin无法阅读完所有的n个章节,输出−1。
样例输入 复制
1 10
3 4 0 6 1 1 0 8 6 3
样例输出 复制
2
提示
数据范围:
本题使用子任务捆绑测试。
对于所有测试数据,保证1≤n≤5×105 ,0≤ai<n。
Subtask 1(10%):1≤n≤10,d=1。
Subtask 2(10%):1≤n≤500,d=2。
Subtask 3(20%):1≤n≤5000,3≤d≤4。
Subtask 4(20%):1≤n≤105,5≤d≤6。
Subtask 5(40%) :1≤n≤5×105,7≤d≤10。