正经题解｜任务-宝石

题解：任务-宝石

题目分析

本题的要求是将 $n$ 种不同的宝石分给 $n$ 个冒险者，且每个冒险者获得的宝石数量互不相同。我们需要计算最少的宝石总数，满足所有冒险者拿到的宝石数量不同。

为满足条件，我们可以设每个冒险者拿到的宝石数量为一个递增的整数序列，即第一个冒险者拿 $1$ 颗宝石，第二个拿 $2$ 颗宝石，第三个拿 $3$ 颗，依此类推，第 $n$ 个冒险者拿 $n$ 颗宝石。

因此，最少的宝石数量就是前 $n$ 个自然数之和，即：
[
S = 1 + 2 + 3 + \dots + n = \frac{n \times (n + 1)}{2}
]
这个公式是等差数列的和，直接代入 $n$ 就可以得到答案。

AC代码

n = int(input())
# 使用等差数列求和公式计算总宝石数
total_gems = n * (n + 1) // 2
print(total_gems)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    cout << (1 + n) * n / 2 << endl;
    return 0;
}

复杂度分析

• 时间复杂度：$O(1)$，因为计算公式中的乘法和除法是常数时间操作。
• 空间复杂度：$O(1)$，只用了常数的空间来存储变量。