OneCoder Avatar
OneCodercoderli.com · 1025 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++五级真题 luogu-P17010 [GESP202606 五级] 排排坐

📅 2026-07-06·✍️ OneCoder·计算中...·⏱️ 6 分钟

GESP C++五级2026年6月真题。本题考查排序与贪心策略,需要分析每个位置对总糖果数的贡献系数,从而确定最优排列方式。难度⭐⭐。本题在洛谷评定为普及-。

luogu-P17010 [GESP202606 五级] 排排坐

题目要求

题目描述

老师正在和小朋友们分糖果。

小朋友们先在自己的手上写一个数字,然后坐成一排。

老师分发糖果的规则是:每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。

现在小朋友们都已经在自己手上写上了数字。

请帮小朋友们安排合适的座位顺序,使得小朋友们分到的糖果总量最大,输出这个最大值。

输入格式

输入 行,

第一行为一个正整数 ,表示小朋友的个数;

第二行为 个正整数 ,表示小朋友们手上的数字,整数之间以空格分隔。

输出格式

输出一个整数,表示小朋友们可能分到的最大糖果总数量。

输入输出样例 #1

输入 #1
PLAINTEXT2 行
5
7 5 8 9 3
输出 #1
PLAINTEXT1 行
111

说明/提示

小朋友安排座位后从左向右每人手上数字依次是:。

这时可以得到最多的糖果:。

数据范围

,。


题目分析

本题表面上是排列问题,但通过数学推导可以转化为一个经典的贪心问题。

1. 推导每个位置的贡献

假设小朋友们从左到右排列为 ,则每个小朋友获得的糖果数为该位置的前缀和:

  • 第 个小朋友得到:
  • 第 个小朋友得到:
  • 第 个小朋友得到:
  • 第 个小朋友得到:

将所有糖果加在一起,统计每个 在总和中出现了多少次:

  • 出现在第 个小朋友的糖果中,共 次
  • 出现在第 个小朋友的糖果中,共 次
  • 出现在第 个小朋友的糖果中,共 次

因此,糖果总量为:

即位置 (从左到右, 开始编号)的贡献系数为 。

2. 贪心策略

由上述公式可知,越靠左的位置贡献系数越大()。为了使总和最大,根据排序不等式(或直觉:大数配大系数),应将数字从大到小排列。

即将最大的数字放在最左边(系数 ),次大的放第二个位置(系数 ),以此类推。

3. 样例验证

数字 降序排列为 ,总糖果数为:

与样例输出一致。

4. 复杂度分析

  • 时间复杂度:排序 ,求和 ,总体
  • 空间复杂度:存储数组

5. 注意事项

  • 数据范围 ,,最大总和约为 ,需要使用 long long 类型存储结果,避免 int 溢出

示例代码

将数字降序排列后,按位置乘以对应的贡献系数累加即可。

C++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;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!