G3018 [GESP202506 三级] 分糖果 题解

知识点：贪心、递推、序列处理。

解题思路

依次分配，第i人的糖果数取max(其最低需求,前一人的数量+1)，累计总数。

为什么正确

每一步取能满足当前要求的最小值，减小前缀不会增加后续下界，故逐步最小可得到总和最小。

易错点

必须严格递增而不是非递减；总和用long long。

复杂度

时间O(n)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    long long cur=0,sum=0,x;
    while(n--) {
        cin>>x;
        cur=max(cur+1,x);
        sum+=cur;
    }
    cout<<sum;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。