生物学中除了DNA序列本身，还有一个非常重要的概念叫 “质粒” 和 “基因工程”。

这道题目考察的是环状模型的线性化处理以及排序的应用，难度定位在 GESP 5级（约等于 CSP-J T2 难度）。

题目：质粒切割计划（Plasmid Cutting）

【背景知识讲解】

在高中生物选修三《现代生物科技专题》中，基因工程是一个核心考点。

1. 质粒（Plasmid）：细菌细胞内一种环状的DNA分子。你可以把它想象成一个圆形的橡皮筋。它是基因工程中常用的“运载体”，用来把外源基因运送到受体细胞里。
2. 限制性核酸内切酶（Restriction Enzyme）：简称“限制酶”，它是基因工程的“分子手术刀”。它能识别双链DNA分子的特定核苷酸序列，并切开磷酸二酯键。

图示： 想象一个时钟（环状DNA）。如果限制酶在“3点钟”和“9点钟”的位置各切一刀，这个环状DNA就会变成两段线性的DNA片段：

• 一段是上半圆（9点 $\to$ 12点 $\to$ 3点）。
• 一段是下半圆（3点 $\to$ 6点 $\to$ 9点）。

【题目描述】

作为基因工程实验室的助手，你需要处理一个周长为 $L$ 的环状质粒DNA。 实验室使用了某种限制酶，在这个质粒上切了 $N$ 刀。 我们用一个坐标系来描述这个质粒：把质粒拉直看作一条线段 $[0, L]$，但请注意，坐标 $0$ 和坐标 $L$ 在环上是连接在一起的同一个点。

现在给出 $N$ 个切割点的位置（坐标值 $0 \le p_i < L$），请计算切割后产生的最长那一段DNA片段的长度是多少。

【输入格式】

第一行包含两个整数 $L$ 和 $N$，分别表示质粒的总周长和切割点的数量。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示每个切割点在质粒上的坐标位置。 注意：输入的坐标位置不一定是按照从小到大的顺序给出的。

【输出格式】

输出一个整数，表示最长片段的长度。

【样例数据】

输入：

100 3
80 10 35

输出：

45

样例解释： 质粒总长 100。切割点分别在 10, 35, 80。

• 片段1：从 10 到 35，长度 $35 - 10 = 25$。
• 片段2：从 35 到 80，长度 $80 - 35 = 45$。
• 片段3（跨越零点）：从 80 到 10，长度 $(100 - 80) + 10 = 30$。 最长的片段是 45。

【数据范围】

• 对于 100% 的数据：$2 \le N \le 100,000$，$N < L \le 1,000,000,000$。
• 坐标位置 $0 \le A_i < L$，且所有 $A_i$ 互不相同。

一、 思路提示

1. 数据的有序性：题目明确说了“输入的坐标不一定有序”。如果你想计算相邻两个切口之间的距离，乱序的数据方便计算吗？
2. 环的处理：这是本题的核心难点。
   • 在数轴上，计算 $A$ 和 $B$ ($A < B$) 的距离很简单，就是 $B - A$。
   • 但是这是一个圆环。除了中间的一段段距离，还有一段“跨越边界”的距离。
   • 想象一下，如果你把这个圆环在坐标 $0$ 处剪断拉直，最左边有一个切点（最小坐标），最右边有一个切点（最大坐标）。它俩之间虽然在数轴上离得最远，但在圆环上，它们是通过“0点/L点”接口相连的。
3. 计算策略：
   • 第一步：让切点变有序。
   • 第二步：计算数组中相邻元素的差值。
   • 第三步：别忘了最后一段（首尾相连的那一段）。

二、 预备知识点总结

要解决这道题，学生需要掌握以下 GESP 5级 / CSP-J 考纲中的知识点：

1. 排序算法：由于 $N$ 高达 $10^5$，必须使用 $O(N \log N)$ 的排序算法（如 std::sort）。
2. 数组/向量的使用：存储切点坐标。
3. 环形问题的线性化：理解如何处理循环结构的边界条件（即 $Tail \to Head$ 的距离计算）。
4. 简单的贪心/最值查找：遍历所有片段长度，维护一个 max_len。

三、 启发式教学：草稿纸上的推理过程

我们再次拿出草稿纸。 教练：“大家画一个圆圈，代表质粒。总周长 $L=100$。”

1. 标记点：

   • “随便点几个点，比如 80, 10, 35。”
   • “为了方便计算，我们在脑子里是不是习惯按顺时针或者从小到大的顺序去数？”
   • 步骤1：先排序。排完序变成了 10, 35, 80。

2. 计算中间段：

   • “从 10 走到 35，走了多少？” $\to$ $35 - 10 = 25$。
   • “从 35 走到 80，走了多少？” $\to$ $80 - 35 = 45$。
   • 通用公式：对于排序后的数组 $A$，第 $i$ 段长度 = $A[i] - A[i-1]$。

3. 突破难点（首尾相连）：

   • “现在到了 80，我们要回到 10，怎么走？”
   • “能不能直接 $10 - 80$？不行，那是负数。”
   • 教练画图引导：

     0/100 (起点/终点)
        |
     ---|--- 80
     |  |
     10
     

   • “从 80 走到 100（也就是0），走了多少？” $\to$ $100 - 80 = 20$。
   • “从 0 走到 10，走了多少？” $\to$ $10$。
   • “合起来是多少？” $\to$ $20 + 10 = 30$。
   • 通用公式：最后一段跨越零点的长度 = $(L - A[N-1]) + A[0]$。

4. 总结算法流程：

   • 读入 $N$ 个点。
   • std::sort 排序。
   • 遍历 $1$ 到 $N-1$，计算 $A[i] - A[i-1]$，不断更新 ans。
   • 单独计算首尾段 $(L - A_{last}) + A_{first}$，更新 ans。
   • 输出 ans。

时间复杂度分析：

• 排序：$O(N \log N)$。
• 遍历一次：$O(N)$。
• 总复杂度：$O(N \log N)$。对于 $N=10^5$，计算量约为 $1.7 \times 10^6$，远小于 $10^8$ 的限制，轻松通过。

四、 读题关键词总结

做这类题时，请圈出以下关键词：

1. “环状” / “周长” $\rightarrow$ 警报！这是环形问题，一定要考虑首尾相连的那一段。
2. “坐标不一定有序” $\rightarrow$ 暗示必须先排序才能进行线性扫描。
3. “最长” $\rightarrow$ 这是一个求最值问题（Maximization）。
4. 数据范围 $L \le 10^9$ $\rightarrow$ 坐标值很大，不能开一个 $10^9$ 大小的 bool 数组来标记（会爆内存），只能存坐标点的位置（离散化思维）。
5. 数据范围 $N \le 10^5$ $\rightarrow$ 要求算法效率至少是 $O(N \log N)$，不能用 $O(N^2)$ 的暴力冒泡排序。

小思考题：如果这题让你求“最短”片段，逻辑是一样的吗？如果有两个切点重合了（虽然题目说互不相同），长度会是多少？（长度为0）。这些都是编程时要考虑的健壮性。