【GESP】C++五级真题 luogu-P17010 [GESP202606 五级] 排排坐
GESP C++五级2026年6月真题。本题考查排序与贪心策略，需要分析每个位置对总糖果数的贡献系数，从而确定最优排列方式。难度⭐⭐。本题在洛谷评定为普及-。
luogu-P17010 [GESP202606 五级] 排排坐
题目要求
题目描述
老师正在和小朋友们分糖果。
小朋友们先在自己的手上写一个数字，然后坐成一排。
老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。
现在小朋友们都已经在自己手上写上了数字。
请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。
输入格式
输入 $2$ 行，
第一行为一个正整数 $n$，表示小朋友的个数；
第二行为 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，表示小朋友们手上的数字，整数之间以空格分隔。
输出格式
输出一个整数，表示小朋友们可能分到的最大糖果总数量。
输入输出样例 #1
输入 #1
1
2
5
7 5 8 9 3
输出 #1
1
111
说明/提示
小朋友安排座位后从左向右每人手上数字依次是：$9, 8, 7, 5, 3$。
这时可以得到最多的糖果：$(9) + (9 + 8) + (9 + 8 + 7) + (9 + 8 + 7 + 5) + (9 + 8 + 7 + 5 + 3) = 111$。
数据范围
$1 \le n \le 1000$，$1 \le a_i \le 1000$。
题目分析
本题表面上是排列问题，但通过数学推导可以转化为一个经典的贪心问题。
1. 推导每个位置的贡献
假设小朋友们从左到右排列为 $a_1, a_2, \cdots, a_n$，则每个小朋友获得的糖果数为该位置的前缀和：
- 第 $1$ 个小朋友得到：$a_1$
- 第 $2$ 个小朋友得到：$a_1 + a_2$
- 第 $3$ 个小朋友得到：$a_1 + a_2 + a_3$
- $\cdots$
- 第 $n$ 个小朋友得到：$a_1 + a_2 + \cdots + a_n$
将所有糖果加在一起，统计每个 $a_i$ 在总和中出现了多少次：
- $a_1$ 出现在第 $1, 2, 3, \cdots, n$ 个小朋友的糖果中，共 $n$ 次
- $a_2$ 出现在第 $2, 3, \cdots, n$ 个小朋友的糖果中，共 $n - 1$ 次
- $a_i$ 出现在第 $i, i+1, \cdots, n$ 个小朋友的糖果中，共 $n - i + 1$ 次
因此，糖果总量为：
\[\text{Total} = n \cdot a_1 + (n-1) \cdot a_2 + (n-2) \cdot a_3 + \cdots + 1 \cdot a_n\]即位置 $i$（从左到右，$1$ 开始编号）的贡献系数为 $n - i + 1$。
2. 贪心策略
由上述公式可知，越靠左的位置贡献系数越大（$n, n-1, \cdots, 1$）。为了使总和最大，根据排序不等式（或直觉：大数配大系数），应将数字从大到小排列。
即将最大的数字放在最左边（系数 $n$），次大的放第二个位置（系数 $n-1$），以此类推。
3. 样例验证
数字 $7, 5, 8, 9, 3$ 降序排列为 $9, 8, 7, 5, 3$，总糖果数为：
\[5 \times 9 + 4 \times 8 + 3 \times 7 + 2 \times 5 + 1 \times 3 = 45 + 32 + 21 + 10 + 3 = 111\]与样例输出一致。
4. 复杂度分析
- 时间复杂度：排序 $O(n \log n)$，求和 $O(n)$，总体 $O(n \log n)$
- 空间复杂度：存储数组 $O(n)$
5. 注意事项
- 数据范围 $n \le 1000$，$a_i \le 1000$，最大总和约为 $1000 \times 1000 \times 1000 = 10^9$，需要使用
long long类型存储结果，避免int溢出
示例代码
将数字降序排列后，按位置乘以对应的贡献系数累加即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
int main() {
int n;
std::cin >> n;
int a[1005];
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
// 降序排列：让最大的数字排在最左边，获得最大的贡献系数
std::sort(a, a + n, std::greater<int>());
// 计算糖果总量
// 排序后 a[0] 是最大值，位于第 1 个位置，贡献系数为 n
// a[1] 位于第 2 个位置，贡献系数为 n - 1
// a[i] 位于第 i+1 个位置，贡献系数为 n - i
long long total = 0;
for (int i = 0; i < n; i++) {
total += (long long)(n - i) * a[i];
}
std::cout << total << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
