给大家分享我 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，不变差。因此最优 d 可以只在：
\left\lfloor \frac m2\right\rfloor+1\le d\le m里找。
3. 在上半段按商分块
令：
L=\left\lfloor \frac m2\right\rfloor+1只枚举 d\in[L,m]。
对固定的商：
q=\left\lfloor \frac nd\right\rfloor所有满足这个商的 d 构成区间：
\left[\left\lfloor\frac n{q+1}\right\rfloor+1,\left\lfloor\frac nq\right\rfloor\right]在同一个 q 内：
n\bmod d+m-d=n-qd+m-d=n+m-(q+1)d显然 d 越大越优，所以每个商只需要检查该区间里的最大 d。
在 d\in[L,m] 中，商的范围是：
q_{\min}=\left\lfloor\frac nm\right\rfloor,\qquad q_{\max}=\left\lfloor\frac nL\right\rfloor由于 L>m/2，所以：
q_{\max}<\frac{2n}{m}也就是说商的数量大约是 O(n/m)。
另一方面，如果 m 很小，直接枚举 d\in[L,m] 只要 O(m)。
所以单次复杂度：
O\left(\min\left(m,\frac nm\right)\right)随机 n,m\in[1,V] 时，期望是 O(\log V)。
4. C++17 代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
int64 solve_one(int64 n, int64 m) {
// 苹果比小朋友少：保留 n 个小朋友，不吃苹果
if (m > n) return m - n;
// n >= m，只需要考虑 d in [L, m]
int64 L = m / 2 + 1;
int64 d_cnt = m - L + 1;
int64 q_min = n / m;
int64 q_max = n / L;
int64 q_cnt = q_max - q_min + 1;
i128 best = (i128)4e18;
// 哪边少枚举哪边
if (d_cnt <= q_cnt) {
// 直接枚举 d
for (int64 d = L; d <= m; d++) {
i128 cur = (i128)(n % d) + (m - d);
if (cur < best) best = cur;
}
} else {
// 按 q = floor(n / d) 分块
for (int64 q = q_min; q <= q_max; q++) {
int64 left = n / (q + 1) + 1;
int64 right = n / q;
left = max(left, L);
right = min(right, m);
if (left <= right) {
int64 d = right; // 同一个 q 内，d 越大越优
i128 cur = (i128)(n % d) + (m - d);
if (cur < best) best = cur;
}
}
}
return (int64)best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> Q;
long long xr = 0;
while (Q--) {
int64 n, m;
cin >> n >> m;
int64 ans = solve_one(n, m);
xr ^= ans;
}
cout << xr << '\n';
return 0;
}
网友解答：
--【壹】--：
看到最近比较火的分苹果题目，想到了之前出的题目，你说这巧不巧
一句话题意：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，不变差。因此最优 d 可以只在：
\left\lfloor \frac m2\right\rfloor+1\le d\le m里找。
3. 在上半段按商分块
令：
L=\left\lfloor \frac m2\right\rfloor+1只枚举 d\in[L,m]。
对固定的商：
q=\left\lfloor \frac nd\right\rfloor所有满足这个商的 d 构成区间：
\left[\left\lfloor\frac n{q+1}\right\rfloor+1,\left\lfloor\frac nq\right\rfloor\right]在同一个 q 内：
n\bmod d+m-d=n-qd+m-d=n+m-(q+1)d显然 d 越大越优，所以每个商只需要检查该区间里的最大 d。
在 d\in[L,m] 中，商的范围是：
q_{\min}=\left\lfloor\frac nm\right\rfloor,\qquad q_{\max}=\left\lfloor\frac nL\right\rfloor由于 L>m/2，所以：
q_{\max}<\frac{2n}{m}也就是说商的数量大约是 O(n/m)。
另一方面，如果 m 很小，直接枚举 d\in[L,m] 只要 O(m)。
所以单次复杂度：
O\left(\min\left(m,\frac nm\right)\right)随机 n,m\in[1,V] 时，期望是 O(\log V)。
4. C++17 代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
int64 solve_one(int64 n, int64 m) {
// 苹果比小朋友少：保留 n 个小朋友，不吃苹果
if (m > n) return m - n;
// n >= m，只需要考虑 d in [L, m]
int64 L = m / 2 + 1;
int64 d_cnt = m - L + 1;
int64 q_min = n / m;
int64 q_max = n / L;
int64 q_cnt = q_max - q_min + 1;
i128 best = (i128)4e18;
// 哪边少枚举哪边
if (d_cnt <= q_cnt) {
// 直接枚举 d
for (int64 d = L; d <= m; d++) {
i128 cur = (i128)(n % d) + (m - d);
if (cur < best) best = cur;
}
} else {
// 按 q = floor(n / d) 分块
for (int64 q = q_min; q <= q_max; q++) {
int64 left = n / (q + 1) + 1;
int64 right = n / q;
left = max(left, L);
right = min(right, m);
if (left <= right) {
int64 d = right; // 同一个 q 内，d 越大越优
i128 cur = (i128)(n % d) + (m - d);
if (cur < best) best = cur;
}
}
}
return (int64)best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> Q;
long long xr = 0;
while (Q--) {
int64 n, m;
cin >> n >> m;
int64 ans = solve_one(n, m);
xr ^= ans;
}
cout << xr << '\n';
return 0;
}
看到最近比较火的分苹果题目，想到了之前出的题目，你说这巧不巧
一句话题意：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，不变差。因此最优 d 可以只在：
\left\lfloor \frac m2\right\rfloor+1\le d\le m里找。
3. 在上半段按商分块
令：
L=\left\lfloor \frac m2\right\rfloor+1只枚举 d\in[L,m]。
对固定的商：
q=\left\lfloor \frac nd\right\rfloor所有满足这个商的 d 构成区间：
\left[\left\lfloor\frac n{q+1}\right\rfloor+1,\left\lfloor\frac nq\right\rfloor\right]在同一个 q 内：
n\bmod d+m-d=n-qd+m-d=n+m-(q+1)d显然 d 越大越优，所以每个商只需要检查该区间里的最大 d。
在 d\in[L,m] 中，商的范围是：
q_{\min}=\left\lfloor\frac nm\right\rfloor,\qquad q_{\max}=\left\lfloor\frac nL\right\rfloor由于 L>m/2，所以：
q_{\max}<\frac{2n}{m}也就是说商的数量大约是 O(n/m)。
另一方面，如果 m 很小，直接枚举 d\in[L,m] 只要 O(m)。
所以单次复杂度：
O\left(\min\left(m,\frac nm\right)\right)随机 n,m\in[1,V] 时，期望是 O(\log V)。
4. C++17 代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
int64 solve_one(int64 n, int64 m) {
// 苹果比小朋友少：保留 n 个小朋友，不吃苹果
if (m > n) return m - n;
// n >= m，只需要考虑 d in [L, m]
int64 L = m / 2 + 1;
int64 d_cnt = m - L + 1;
int64 q_min = n / m;
int64 q_max = n / L;
int64 q_cnt = q_max - q_min + 1;
i128 best = (i128)4e18;
// 哪边少枚举哪边
if (d_cnt <= q_cnt) {
// 直接枚举 d
for (int64 d = L; d <= m; d++) {
i128 cur = (i128)(n % d) + (m - d);
if (cur < best) best = cur;
}
} else {
// 按 q = floor(n / d) 分块
for (int64 q = q_min; q <= q_max; q++) {
int64 left = n / (q + 1) + 1;
int64 right = n / q;
left = max(left, L);
right = min(right, m);
if (left <= right) {
int64 d = right; // 同一个 q 内，d 越大越优
i128 cur = (i128)(n % d) + (m - d);
if (cur < best) best = cur;
}
}
}
return (int64)best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> Q;
long long xr = 0;
while (Q--) {
int64 n, m;
cin >> n >> m;
int64 ans = solve_one(n, m);
xr ^= ans;
}
cout << xr << '\n';
return 0;
}
网友解答：
--【壹】--：
看到最近比较火的分苹果题目，想到了之前出的题目，你说这巧不巧
一句话题意：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，不变差。因此最优 d 可以只在：
\left\lfloor \frac m2\right\rfloor+1\le d\le m里找。
3. 在上半段按商分块
令：
L=\left\lfloor \frac m2\right\rfloor+1只枚举 d\in[L,m]。
对固定的商：
q=\left\lfloor \frac nd\right\rfloor所有满足这个商的 d 构成区间：
\left[\left\lfloor\frac n{q+1}\right\rfloor+1,\left\lfloor\frac nq\right\rfloor\right]在同一个 q 内：
n\bmod d+m-d=n-qd+m-d=n+m-(q+1)d显然 d 越大越优，所以每个商只需要检查该区间里的最大 d。
在 d\in[L,m] 中，商的范围是：
q_{\min}=\left\lfloor\frac nm\right\rfloor,\qquad q_{\max}=\left\lfloor\frac nL\right\rfloor由于 L>m/2，所以：
q_{\max}<\frac{2n}{m}也就是说商的数量大约是 O(n/m)。
另一方面，如果 m 很小，直接枚举 d\in[L,m] 只要 O(m)。
所以单次复杂度：
O\left(\min\left(m,\frac nm\right)\right)随机 n,m\in[1,V] 时，期望是 O(\log V)。
4. C++17 代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
int64 solve_one(int64 n, int64 m) {
// 苹果比小朋友少：保留 n 个小朋友，不吃苹果
if (m > n) return m - n;
// n >= m，只需要考虑 d in [L, m]
int64 L = m / 2 + 1;
int64 d_cnt = m - L + 1;
int64 q_min = n / m;
int64 q_max = n / L;
int64 q_cnt = q_max - q_min + 1;
i128 best = (i128)4e18;
// 哪边少枚举哪边
if (d_cnt <= q_cnt) {
// 直接枚举 d
for (int64 d = L; d <= m; d++) {
i128 cur = (i128)(n % d) + (m - d);
if (cur < best) best = cur;
}
} else {
// 按 q = floor(n / d) 分块
for (int64 q = q_min; q <= q_max; q++) {
int64 left = n / (q + 1) + 1;
int64 right = n / q;
left = max(left, L);
right = min(right, m);
if (left <= right) {
int64 d = right; // 同一个 q 内，d 越大越优
i128 cur = (i128)(n % d) + (m - d);
if (cur < best) best = cur;
}
}
}
return (int64)best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> Q;
long long xr = 0;
while (Q--) {
int64 n, m;
cin >> n >> m;
int64 ans = solve_one(n, m);
xr ^= ans;
}
cout << xr << '\n';
return 0;
}