题解

题目解析

• 输入输出：第一行输入整数 $n$ 表示小朋友数量，第二行输入 $n$ 个正整数 $a_i$ 表示每位小朋友的最小需求。输出最少需要的糖果总数。
• 数据范围：$1 \le n \le 1000$，$1 \le a_i \le 10^9$。注意结果可能超过 $32$ 位整数范围（如样例2所示）。
• 复杂度要求：时间复杂度 $O(n)$，空间复杂度 $O(1)$，需使用 $64$ 位整数（long long）存储结果。
• 算法知识点：贪心算法、序列处理、数据范围分析

思路解析

1. 问题建模：设第 $i$ 位小朋友实际获得 $b_i$ 颗糖果，需满足：$b_i \ge a_i$（最小需求），且 $b_i > b_{i-1}$（严格递增，即 $b_i \ge b_{i-1} + 1$）。
2. 贪心策略：为使总和最小，每位小朋友在满足约束前提下应取最小可能值。对于第 $i$ 位，$b_i = \max(a_i, b_{i-1} + 1)$，即同时满足自身最小需求和比前一位多 $1$ 的要求。
3. 递推实现：维护变量 $\textit{pre\_num}$ 表示前一位小朋友实际获得的糖果数（初始为 $-1$，确保第一位至少取 $a_1$）。遍历每位小朋友时，计算当前分配值 $\textit{cur} = \max(a_i, \textit{pre\_num} + 1)$，累加至总和，并更新 $\textit{pre\_num}$。
4. 数据类型选择：由于 $n \le 1000$ 且 $a_i \le 10^9$，最坏情况下总和可能超过 $2 \times 10^9$（如样例2），必须使用 long long 避免溢出。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 使用long long防止溢出：n最大1000，但a_i最大1e9，累加和可能超过int范围
    long long pre_num = -1;  // 前一位的糖果数，初始-1确保第一位至少满足a_i
    long long cur_num;       // 当前位的最小需求
    long long sum = 0;       // 糖果总数
    
    for (int i = 1; i <= n; i++) {
        cin >> cur_num;
        // 关键：当前分配数 = max(自身最小需求, 前一位+1)
        // 既满足a_i约束，又满足严格递增约束
        pre_num = max(cur_num, pre_num + 1);
        sum += pre_num;
    }
    cout << sum << endl;
    return 0;
}