B4359 [GESP202506 三级] 分糖果

chen_zhe · 2025-07-27 11:52:05 · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

每个小朋友的糖果数量不仅取决于他自己的愿望，还受到了前一位小朋友的影响。具体来说，第 i 个小朋友的糖果数量必须满足两个条件：一是要大于等于他自己想要的数量 a_i，二是要严格大于前一位小朋友（第 i-1 位）得到的糖果数量。为了让总糖果数最少，我们应该给每个小朋友分发满足这两个条件的、尽可能少的糖果。

我们可以从第一个小朋友开始，依次确定每个小朋友应该分到多少糖果：

• 对于第一个小朋友，他没有前一位小朋友，所以只需要满足自己的要求即可。为了节省糖果，我们应该就给他 a_1 颗。
• 接着看第二个小朋友。他需要的糖果数，首先要大于等于 a_2，其次要比第一个小朋友的糖果数（也就是 a_1）更多。比 a_1 更多，意味着至少是 a_1 + 1 颗。所以，第二个小朋友至少需要 a_2 和 a_1 + 1 这两者中的较大值。为了省糖果，我们就给他这个较大值，不多给。
• 以此类推……

这个规律可以推广到所有小朋友。对于第 i 个小朋友，我们假设已经确定了前一位（第 i-1 位）小朋友拿到了 p 颗糖果。那么第 i 个小朋友需要的糖果数，既要满足他自己的愿望（不小于 a_i），又要比前一位多（不小于 p + 1）。因此，我们应该给他 a_i 和 p + 1 中的较大值。

按照这个思路，我们从头到尾遍历一遍所有小朋友，依次计算出每个人最少需要分得的糖果数，并将它们累加起来，就是最终答案。

:::warning

需要特别注意的是，题目中 a_i 的值很大，累加后的总和可能会超过普通整数（int）的表示范围，因此在程序中需要使用能表示更大数值范围的 long long 类型来存储糖果总数和每一位小朋友的糖果数，以避免计算结果溢出。

:::

参考代码：

long long tot = 0, prv = 0; // 第一个小朋友前面没有人，可以认为前一位的糖果数是 0
for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    long long cur = ________; // 当前小朋友需要的糖果数
    ________; // 想想看，还要做什么呢？
}
cout << ________ << endl;