SP4160 MA1 - A1 Road

题目描述

我们的国家依赖高速公路进行连接，这些高速公路需要定期进行维修。一个由政府选定的委员会致力于通过寻找需要修复的首个损坏点，来持续改善名为“A1”的主要高速公路的状况。

从首个损坏点开始，高速公路被划分为等长的段。我们将派遣维修队到每个有损坏的段进行修复。因为损坏点通常比维修队的数量多，所以最好以某种方式将高速公路划分为固定长度的段，使得包含损坏的段数尽可能少。

高速公路上共有 $N$ 个损坏点，每个损坏点的位置是一个整数，表示它离高速公路起点的距离（单位：米）。每段的长度为 $M$ 米。在最开始的 $M$ 米内没有任何损坏点。第一段必须在最初的 $M$ 米范围内开始。如果第一段从第 $K$ 米处开始，那么第 $L$ 段将从第 $(K + (L-1) \times M)$ 米处开始。在一个段内，从段的第一米至最后一米之间的所有损坏点都可以被修复。

请编写一个程序，找出修复“A1”高速公路上所有损坏点所需的最少维修队数目，并列出第一段可以开始的所有可能起始位置。

输入格式

输入的第一行包含两个整数 $M$ 和 $N$，用空格分隔，$1 \leq M, N \leq 100\,000$。其中 $M$ 是每段的长度，$N$ 是高速公路上损坏点的数量。

第二行包含 $N$ 个整数，用空格分隔，表示所有损坏点的位置。每个数字都大于 $M$ 并且小于或等于 $2\,000\,000\,000$。这些数字严格递增。

输出格式

输出的第一行应包含修复所有损坏点所需的最少维修队数。

第二行应列出第一段可以开始的所有位置，这些数字之间应以空格分隔，并且必须是严格递增的序列。

3 5 
4 5 7 8 9 

2
1

说明/提示

• $1 \leq M, N \leq 100\,000$
• $M < \text{损坏点位置} \leq 2\,000\,000\,000$

本翻译由 AI 自动生成