P6485 [COCI2010-2011#4] PROSJEK
Flanksy
·
·
题解
若 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，将选择的数两两配对后考虑对答案的影响。
| 1 |
2 |
3 |
4 |
5 |
| 1 |
1 |
1.5 |
2 |
2.5 |
3 |
| 2 |
1.5 |
2 |
2.5 |
3 |
3.5 |
| 3 |
2 |
2.5 |
3 |
3.5 |
4 |
| 4 |
2.5 |
3 |
3.5 |
4 |
4.5 |
| 5 |
3 |
3.5 |
4 |
4.5 |
5 |
可以发现只需要 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 的值。