luogu-B4359 [GESP202506 三级] 分糖果

GESP C++三级，2025年6月真题，模拟算法，难度★★☆☆☆。 本次三级题目个人感觉比较简单。

luogu-B4359 [GESP202506 三级] 分糖果

题目要求

题目描述

有 $n$ 位小朋友排成一队等待老师分糖果。第 $i$ 位小朋友想要至少 $a_i$ 颗糖果，并且分给他的糖果数量必须比分给前一位小朋友的糖果数量更多，不然他就会不开心。

老师想知道至少需要准备多少颗糖果才能让所有小朋友都开心。你能帮帮老师吗？

输入格式

第一行，一个正整数 $n$，表示小朋友的人数。

第二行，$n$ 个正整数 $a_1, a_2, \ldots, a_n$，依次表示每位小朋友至少需要的糖果数量。

输出格式

输出一行，一个整数，表示最少需要准备的糖果数量。

输入输出样例 #1

输入 #1

4
1 4 3 3

输出 #1

16

输入输出样例 #2

输入 #2

15
314 15926 53589793 238462643 383279502 8 8 4 1 9 7 1 6 9 3

输出 #2

4508143253

说明/提示

对于所有测试点，保证 $1 \leq n \leq 1000$，$1 \leq a_i \leq 10^9$。

题目分析

解题思路

本题的解题思路如下：

1. 问题本质：

   • 输入一个正整数 $n$ 表示小朋友的数量
   • 输入 $n$ 个正整数 $a_i$，表示每个小朋友至少需要的糖果数
   • 要求每个小朋友分到的糖果数必须严格大于前一个小朋友的糖果数
   • 求满足条件的最少总糖果数

2. 解题关键：

   • 核心思路：
     1. 遍历每个小朋友：
        • 记录前一个小朋友分到的糖果数 last_count
        • 当前小朋友至少需要 $a_i$ 颗糖果
     2. 分配策略：
        • 如果 $a_i$ > last_count，直接分配 $a_i$ 颗糖果
        • 否则分配 last_count + 1 颗糖果
     3. 累加总糖果数：
        • 每次分配后将糖果数加入总和
        • 更新 last_count 为当前分配的糖果数

3. 复杂度分析：

   • 时间复杂度：$O(n)$，只需要遍历一次所有小朋友
   • 空间复杂度：$O(1)$，只需要常数级别的变量存储

{% include custom/custom-post-content-inner.html %}

示例代码

#include <iostream>

int main() {
    // 读取小朋友的数量
    int n;
    std::cin >> n;
    
    // 总糖果数和上一个小朋友分到的糖果数
    long long sum = 0;
    int last_count = 0;
    
    // 遍历每个小朋友
    for (int i = 0; i < n; i++) {
        // 读取当前小朋友至少需要的糖果数
        int a;
        std::cin >> a;
        
        // 如果当前小朋友需要的糖果数大于前一个小朋友的糖果数
        if (a > last_count) {
            // 直接分配所需的糖果数
            sum += a;
            last_count = a;
        } else {
            // 否则分配比前一个小朋友多一个的糖果数
            sum += last_count + 1;
            last_count = last_count + 1;
        }
    }
    
    // 输出最少需要的总糖果数
    std::cout << sum << std::endl;
    return 0;
}        

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号