数轴法：一种可能的做题思路（以分糖果一题为例）

· · 算法·理论

前言：笔者在研究 CSP-J 2021 分糖果 时，突发奇想出来的做法。觉得可以作为一种做题的思路于是就记录了下来。

魔改版题面（不要看了不要看了不要看了不要看了不要看了）：

那维莱特是一只可爱的小海獭，他不知道在枫丹的哪个地方发现了 + \infty 颗糖果，设 k 为他可以拿走的糖果数量，则 k 必须满足 L \le k \le R。因为美露莘喜欢吃糖（？），所以他必须分成 n 份。求分完所有糖之后剩下的糖的数量。

根据除数的定义，a \bmod n 的最大值应该是 n-1，所以我们定义“最优点 P”为 n-1。

首先考虑 R-L+1 \ge n 的情况。以样例 1：n=7,L=16,R=23 为例，画一个数轴（横坐标 k 表示取了多少个糖果）：

可以猜想：当 L,R 距离大于等于 n，即 R-L+1 \ge n 时，线段 L,R 一定可以包住一个最优点。实际上可以利用数学知识证明，在此处不再赘述。

接下来考虑 R-L+1 < n 的情况。这可以分为两种情况讨论：一种是数轴可以包住一个最优点，一种是最优点不在线段 LR 内。画图分析：

最优点在线段内，考虑 n=8,L=13,R=17，此时有 L \bmod n > R \bmod n，应取 k=14 颗糖果：

最优点在线段外，考虑 n=22,L=13,R=17，此时应取 k=17 \bmod 22=17 颗糖果：

综上，要使得自己分到的糖果数量最多，取走的糖果数量 k 应满足：

上述结论均可证明。

可以尝试使用该方法完成的题目：