C++ 算法考级专栏
🎨 视觉封面【GESP】C++五级真题 luogu-P17010 [GESP202606 五级] 排排坐
GESP C++五级2026年6月真题。本题考查排序与贪心策略,需要分析每个位置对总糖果数的贡献系数,从而确定最优排列方式。难度⭐⭐。本题在洛谷评定为普及-。
luogu-P17010 [GESP202606 五级] 排排坐
题目要求
题目描述
老师正在和小朋友们分糖果。
小朋友们先在自己的手上写一个数字,然后坐成一排。
老师分发糖果的规则是:每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。
现在小朋友们都已经在自己手上写上了数字。
请帮小朋友们安排合适的座位顺序,使得小朋友们分到的糖果总量最大,输出这个最大值。
输入格式
输入 行,
第一行为一个正整数 ,表示小朋友的个数;
第二行为 个正整数 ,表示小朋友们手上的数字,整数之间以空格分隔。
输出格式
输出一个整数,表示小朋友们可能分到的最大糖果总数量。
输入输出样例 #1
输入 #1
5
7 5 8 9 3输出 #1
111说明/提示
小朋友安排座位后从左向右每人手上数字依次是:。
这时可以得到最多的糖果:。
数据范围
,。
题目分析
本题表面上是排列问题,但通过数学推导可以转化为一个经典的贪心问题。
1. 推导每个位置的贡献
假设小朋友们从左到右排列为 ,则每个小朋友获得的糖果数为该位置的前缀和:
- 第 个小朋友得到:
- 第 个小朋友得到:
- 第 个小朋友得到:
- 第 个小朋友得到:
将所有糖果加在一起,统计每个 在总和中出现了多少次:
- 出现在第 个小朋友的糖果中,共 次
- 出现在第 个小朋友的糖果中,共 次
- 出现在第 个小朋友的糖果中,共 次
因此,糖果总量为:
即位置 (从左到右, 开始编号)的贡献系数为 。
2. 贪心策略
由上述公式可知,越靠左的位置贡献系数越大()。为了使总和最大,根据排序不等式(或直觉:大数配大系数),应将数字从大到小排列。
即将最大的数字放在最左边(系数 ),次大的放第二个位置(系数 ),以此类推。
3. 样例验证
数字 降序排列为 ,总糖果数为:
与样例输出一致。
4. 复杂度分析
- 时间复杂度:排序 ,求和 ,总体
- 空间复杂度:存储数组
5. 注意事项
- 数据范围 ,,最大总和约为 ,需要使用
long long类型存储结果,避免int溢出
示例代码
将数字降序排列后,按位置乘以对应的贡献系数累加即可。
#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:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP】C++五级/四级练习题 luogu-P1413 坚果保龄球
GESP C++ 五级/四级练习题,贪心思想思想考点,四级考生也可以练习,因为难度不大。题目难度⭐⭐★☆☆,适合五级入门和四级练习,洛谷难度等级普及-。
【GESP】C++五级真题(贪心考点) luogu-B3872 [GESP202309 五级] 巧夺大奖
GESP C++ 2023年9月五级真题,贪心算法考点,难度⭐⭐⭐☆☆。洛谷难度等级普及/提高−
【GESP】C++五级真题(贪心和剪枝思想) luogu-B3930 [GESP202312 五级] 烹饪问题
GESP C++ 2023年12月五级真题,贪心和剪枝思想考点,难度⭐⭐⭐☆☆。洛谷难度等级普及/提高−
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

