Moe's CF Life

喵~ 各位好呀！今天本猫娘要给大家带来的是一道关于分糖果的题目，Codeforces 1283B - Candies Division。这道题就像给小猫们分小鱼干一样，要分得又多又公平，一起来看看怎么回事吧！

题目大意

圣诞老人有 n 颗糖果，要分给 k 个小朋友。他想尽可能多地把糖果分出去，但是有几个规矩要遵守，喵~

假设分完之后，拿到最少糖果的小朋友拿了 a 颗，拿得最多的小朋友拿了 b 颗。必须同时满足下面两个条件：

b 和 a 的差距不能太大，最多只能差 1，也就是 b - a <= 1。这意味着，小朋友们拿到的糖果数要么都一样，要么只相差一颗。不能有的小朋友拿一大堆，有的小朋友却很可怜，喵。
拿到 a+1 颗糖果（也就是拿到较多糖果）的小朋友，人数不能超过总人数的一半，即不能超过 ⌊k/2⌋（k 除以 2 向下取整）。

我们的任务是，在满足这些规矩的前提下，计算出圣诞老人最多能分出去多少颗糖果。

举个例子，19 颗糖果分给 4 个小朋友。

k=4, ⌊k/2⌋ = 2。所以拿到比较多糖果的小朋友最多只能有 2 个。
我们可以这样分：[5, 5, 4, 4]。这里 a=4, b=5。b-a=1，满足条件1。拿到 a+1=5 颗糖果的小朋友有 2 个，2 <= ⌊4/2⌋，满足条件2。总共分出去了 5+5+4+4 = 18 颗糖果。这是最优解了喵。

题解方法

要想分出去的糖果最多，那我们肯定希望每个小朋友拿到的糖果都尽可能多，对吧喵？

我们可以分两步来考虑这个问题，就像猫猫捕猎一样，先悄悄接近，再发起总攻！

基础分配 (打好基础喵)：首先，为了满足第一个条件 b - a <= 1，最简单的方法就是先让每个小朋友都拿到一样多的糖果。这个基础数量是多少呢？当然是 n / k（整除）啦。这样，k 个小朋友每人都拿到了 n / k 颗糖果。此时，我们已经分出去了 (n / k) * k 颗糖果。这些糖果就是我们的“保底”部分，每个小朋友都一样多，非常公平。
额外分配 (锦上添花喵)：进行完基础分配后，圣诞老人手里可能还剩下一些糖果。剩下多少呢？就是 n % k（n 除以 k 的余数）。现在我们可以把这些剩下的糖果，一颗一颗地分给一些小朋友，让他们拿到的糖果数从 n / k 变成 (n / k) + 1。这样做之后，小朋友们拿到的糖果数就只有 n / k 和 (n / k) + 1 两种了，完美地满足了 b - a <= 1 的条件（此时 a = n/k, b = n/k + 1）。
但是！别忘了第二个条件：拿到 a+1 颗糖果（也就是 (n/k) + 1 颗）的小朋友数量不能超过 k/2。这意味着，我们最多只能给 k/2 个小朋友发额外的糖果。
所以，我们能分出去的额外糖果数量，取决于两个限制：
- 我们手里剩下的糖果数量：n % k
- 可以拿到额外糖果的人数上限：k / 2
我们能给出的额外糖果数，就是这两个值中较小的那一个，即 min(n % k, k / 2)。
总结一下思路：
- 总共能分出去的糖果 = 基础分配的糖果 + 额外分配的糖果
- 总数 = (n / k) * k + min(n % k, k / 2)
咦？(n / k) * k + (n % k) 不就是 n 嘛？所以，如果 n % k <= k / 2，那么我们可以把所有剩下的糖果都分出去，总数就是 (n / k) * k + (n % k)，也就是 n 本身。如果 n % k > k / 2，那么我们最多只能再分给 k / 2 个小朋友一人一颗，总数就是 (n / k) * k + k / 2。
这两种情况可以合并成一个公式：min(n, (n / k) * k + k / 2)。不过，还是第一种思路更直观，也更好写代码喵~

题解代码

下面是 C++ 的实现代码，加上了本猫娘的思路注释哦~

cpp

#include <iostream>
#include <algorithm>

// 这个函数用来解决一个测试用例喵
void solve() {
    long long n, k;
    std::cin >> n >> k;

    // 我们的目标是最大化分出去的糖果总数
    // 同时要满足两个条件：
    // 1. 小朋友们拿到的糖果数最多差1
    // 2. 拿到 a+1 颗糖果的小朋友数不能超过 k/2

    // 为了让总数最大，我们先让每个小朋友拿到的基础糖果数尽可能多
    // 这个基础数量就是 n / k (整除)
    // 这样，每个小朋友至少能拿到 a = n / k 颗糖果
    long long base_val = n / k;
    long long base_distributed = base_val * k;

    // 基础分配后，我们手里还剩下 n % k 颗糖果
    long long remaining_candies = n % k;

    // 现在，我们可以把剩下的糖果分给一些小朋友，让他们拿到 a+1 颗
    // 但是，拿到 a+1 颗糖果的小朋友人数不能超过 k/2
    long long max_extra_kids = k / 2;

    // 所以，我们能额外分出去的糖果数，取决于“剩下的糖果数”和“人数上限”哪个更小
    long long extra_candies_to_give = std::min(remaining_candies, max_extra_kids);

    // 最终的总数 = 基础分配的总数 + 额外能分的糖果数
    long long total_candies = base_distributed + extra_candies_to_give;

    std::cout << total_candies << "\n";
}

int main() {
    // 为了快一点，加上这两行，处理很多组输入的时候很有用喵
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但里面藏着一些很有用的小知识点，就像藏在猫抓板里的小零食一样！

整除 (/) 与取余 (%)
- 在 C++ (以及很多其他语言) 中，两个整数相除 / 会得到一个整数结果，小数部分会被直接丢掉。例如 19 / 4 的结果是 4。这在计算“每个个体平均能分到多少”的场景下非常方便，正好帮我们算出了保底糖果数 a。
- 取余运算符 % 则是计算除法后的余数。19 % 4 的结果是 3。它完美地帮我们算出了基础分配后还剩下多少零散的资源。这两个操作符是处理这类分配问题的黄金搭档，喵~
贪心思想 (Greedy Approach) 我们的解题思路其实就是一种“贪心”策略。贪心算法的核心是，在每一步决策时，都采取当前状态下最好或最优的选择，从而希望能导致全局最好或最优解。在这个问题里：
- 第一步贪心：为了让总数最大，我们先让每个人的基础值（a）尽可能大，所以我们选择了 n / k。
- 第二步贪心：在满足限制的条件下，我们把剩下的糖果尽可能多地分出去。幸运的是，对于这道题，这种每一步都求最优的贪心策略，恰好可以得到全局最优解。
std::min 函数 这是 C++ 标准库 <algorithm> 里的一个方便函数，可以返回两个（或更多）参数中最小的那个。在代码里，std::min(remaining_candies, max_extra_kids) 简洁地表达了“能分的额外糖果数取决于剩余糖果和人数上限中的较小者”这一逻辑，让代码更清晰易读，喵~

好啦，今天的题解就到这里！希望大家都能明白怎么帮圣诞老人分糖果了。下次再见，喵~ (ฅ'ω'ฅ)

题目大意 ​

题解方法 ​

题解代码 ​

知识点介绍 ​

题目大意

题解方法

题解代码

知识点介绍