给大家分享我 4 年元宵节原创的切小朋友分苹果算法题

问题描述：

看到最近比较火的分苹果题目，想到了之前出的题目，你说这巧不巧

一句话题意：n 个苹果 m 个小朋友，可以一刀切掉一个小朋友 / 一口吃一个苹果，求最少几次操作平分。

加载中... (学校OJ)
image2526×1674 355 KB
image1820×1536 181 KB

题解…已经忘了，不过可以试一试问 AI，有一个根号的做法，也有一个随机数据下期望 log（最坏退化到根号）的做法

补充一下GPT题解，仅供参考，还没时间验证，感兴趣的可以自己看看，不过这题也没啥意思：

1. 化式

最终保留 d 个小朋友，必须 1\le d\le \min(n,m)。

苹果数要变成 d 的倍数，最少吃掉：

n\bmod d

小朋友要砍掉：

m-d

所以单次询问答案是：

\operatorname{ans}(n,m)=\min_{1\le d\le \min(n,m)} \left(n\bmod d+m-d\right)

如果 m>n，显然最优是保留 d=n 个小朋友，不吃苹果：

\operatorname{ans}=m-n

下面只考虑 n\ge m。

---

2. 关键引理：只需考虑 d>m/2

设某个方案保留 d\le m/2 个小朋友，每人分 k 个苹果，即保留苹果数是 kd。

因为 2d\le m，考虑改成保留 2d 个小朋友。

如果 k 是偶数，令每人分 k/2 个苹果，则保留苹果数仍是 kd，但小朋友更多，操作数更少。

如果 k 是奇数且 k\ge 3，令每人分 (k-1)/2 个苹果，则保留苹果数变成 (k-1)d，少了 d 个苹果，但多保留了 d 个小朋友，总操作数不变。

如果 k=1，因为 n\ge m\ge 2d，保留 2d 个小朋友、每人 1 个苹果也是合法的，而且更优。

所以任何 d\le m/2 都可以替换成 2d，不变差。