B4359 [GESP202506 三级] 分糖果

欢迎报名洛谷网校，期待和大家一起进步！

每个小朋友的糖果数量不仅取决于他自己的愿望，还受到了前一位小朋友的影响。具体来说，第

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 类型来存储糖果总数和每一位小朋友的糖果数，以避免计算结果溢出。

参考代码：

CPP

long long tot = 0;
long long prv = 0; // 第一个小朋友前面没有人，可以认为前一位的糖果数是 0
for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    long long cur = max((long long)a, prv + 1); // 取较大值
    tot += cur;
    prv = cur;
}
cout << tot << endl;

B4359 [GESP202506 三级] 分糖果

文章操作

相关推荐

评论

B4359 [GESP202506 三级] 分糖果