[GDKOI2024 普及组] 读书

Luogu

IDLGP10077

Time1000ms

Memory512MB

DifficultyP4

2024广东O2优化

Zayin 是一个热爱读书的学生。最近，Zayin 收到了一本有 $n$ 个章节的书，其中每个章节 $i$ 都有一个限制：她必须至少阅读了其他 $a_i$ 个章节，才能够获取足够的智慧来读懂该章节。每天，Zayin 都会从头到尾开始阅读这本书。对于她还不能读懂的章节（由于限制）或是已经阅读过的章节，Zayin 会在那天跳过它们。现在，Zayin 想要知道至少需要多少天才能阅读完所有的 $n$ 个章节。 ## Input 第一行包含两个整数 $d, n$，表示测试点编号和章节数。第二行包含 $n$ 个整数 $a_i (0 \leq a_i < n)$，表示限制。 ## Output 输出一行包含一个整数，表示最少需要的天数。如果 Zayin 无法阅读完所有的 $n$ 个章节，输出 $-1$。 [samples] ## Note **本题使用子任务捆绑测试。** 对于所有测试数据，保证 $1 \leq n \leq 5 \times 10^5 , 0 \leq a_i < n$。 - Subtask 1（10%）：$1 ≤ n ≤ 10$，$d = 1$。 - Subtask 2（10%）：$1 ≤ n ≤ 500$，$d = 2$。 - Subtask 3（20%）：$1 ≤ n ≤ 5000$，$3 \leq d \leq 4$。 - Subtask 4（20%）：$1 ≤ n ≤ 10^5$，$5 \leq d \leq 6$。 - Subtask 5（40%）：$1 ≤ n ≤ 5 \times 10^5$，$7 \leq d \leq 10$。

Samples

Input #1

1 10
3 4 0 6 1 1 0 8 6 3

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[GDKOI2024 普及组] 读书",
    "description": {
      "content": "Zayin 是一个热爱读书的学生。 最近，Zayin 收到了一本有 $n$ 个章节的书，其中每个章节 $i$ 都有一个限制：她必须至少阅读了其他 $a_i$ 个 章节，才能够获取足够的智慧来读懂该章节。 每天，Zayin 都会从头到尾开始阅读这本书。对于她还不能读懂的章节（由于限制）或是已经阅读过的章节，Zayin 会在那天跳过它们。 现在，Zayin 想要知道至少需要多少天才能阅读完所有的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10077"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Zayin 是一个热爱读书的学生。\n\n最近，Zayin 收到了一本有 $n$ 个章节的书，其中每个章节 $i$ 都有一个限制：她必须至少阅读了其他 $a_i$ 个\n章节，才能够获取足够的智慧来读懂该章节。\n\n每天，Zayin 都会从头到尾开始阅读这本书。对于她还不能读懂的章节（由于限制）或是已经阅读过的章节，Zayin 会在那天跳过它们。\n\n现在，Zayin 想要知道至少需要多少天才能阅读完所有的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments