自动搬运

查看原文

来自洛谷，原作者为

	Flanksy Where we gonna go?

搬运于2025-08-24 22:21:14，当前版本为作者最后更新于2024-02-15 11:58:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

若 $P$ 不为整数，那么必然存在一组仅使用 $\lfloor P \rfloor$ 和 $\lceil P \rceil$ 且使用数字数量最小的方案。

使用其他数字的最优方案中其他数字可以被等价转换为 $\lfloor P \rfloor$ 和 $\lceil P \rceil$ 的组合。

证明：假设给定的 $P \in [2,3]$，此时 $\lfloor P \rfloor=2,\lceil P \rceil=3$，将选择的数两两配对后考虑对答案的影响。

可以发现只需要 $2$ 和 $3$ 的组合就能凑出 $[2,3]$ 区间内的任意数字，其他数对要么和 $2,3$ 组合出的数对等价，要么显然更劣。所以必定存在选择了不超过一个 $2,3$ 之外的数字的最优方案。

再证明包含一个 $2,3$ 之外的数字的最优方案中该数字可以被替换，假设一个最优方案中包含一个 $1$，那么这个方案必定也包含至少一个 $3$，否则能够推出 $P \in [1,2)$，与给定条件矛盾。由上表可知 $1,3$ 等价于 $2,2$，最优方案中包含一个 $4$ 的情况同理。最优方案中不会仅包含一个 $5$，因为 $2,5$ 和 $3,5$ 都是会使答案变劣的组合。

给定的 $P$ 在其他区间内的情况同理，证毕。

令 $x=P - \lfloor P \rfloor$，问题转化为找到一组和最小且满足 $\dfrac{0 \times k_1 + 1 \times k_2}{k_1+k_2}=x$ 的整数 $k_1,k_2$，构造的最优方案中仅使用 $k_1$ 个 $\lfloor P \rfloor$ 和 $k_2$ 个 $\lceil P \rceil$。

移项得 $\dfrac{k_1}{k_2}=\dfrac{1-x}{x}$，令 $y=1-x$，将 $x$ 和 $y$ 同乘 $10$ 的幂转化为整数后同时除以 $\gcd(x,y)$ 可以得到 $k_1,k_2$ 的值。