题解：P14566 【MX-S12-T1】取模

· · 题解

题意

给定一个非负整数序列 a，选定一个正整数 p，使得 a 中所有元素对 p 取模后极差最大，输出这个最大的极差。

思路

我们要使这个极差最大，就要让最小值尽可能地小。

显然，只要将一个数对 p 取模，那么最终结果必定小于 p。

因此仅有 p \ge \max_{i = 1}^n a_i 的时候存在最优解，因为如果 p 再往小的取，那么最大值只会越来越小，极差无法得到最大化。

如果 p > \max_{i = 1}^n a_i，那么所有数对 p 取模最终结果都不变，此时极差为 (\max_{i = 1}^n a_i) - (\min_{i = 1}^n a_i)。

如果 p = \max_{i = 1}^n a_i，那么由于最大值与 p 相等，取模后最大值就会变为 0。此时原来的严格次大值变为最大值，原来的最大值变为最小值，极差为该序列的严格次大值。

最终答案取两种情况的最大值即可。

Code

代码简单，就不放了。