题源：洛谷 P17010 [GESP202606 五级] 排排坐
https://www.luogu.com.cn/problem/P17010

背景

你有没有想过，同样一组数字，换个顺序排一排，结果能差出多少？

在算法竞赛里，这类"排排坐"问题看似只是简单的排序，实则藏着贪心思想的精髓——不是盲目排序，而是要让每个数字的"话语权"最大化。GESP五级这道题，就是一道非常经典的入门贪心题：老师给小朋友分糖果，规则是每个小朋友获得自己及左侧所有小朋友数字之和的糖果数。目标很简单：让总糖果数最大。

这类问题在竞赛中定位明确，属于普及-难度，考察的是选手能否从"排序"这个动作中提炼出贡献度分析的思维方式。很多初学者会直觉地想"把大的放前面"，但很少能说出"为什么"。本文就带你从直觉走向证明，彻底搞懂这类问题的底层逻辑。

核心思想

问题本质：前缀和的总和

题目要求最大化总糖果量。设座位顺序为 b1, b2, …, bn，则：

• 第1个小朋友获得：b1
• 第2个小朋友获得：b1 + b2
• 第3个小朋友获得：b1 + b2 + b3
• …
• 总糖果量：sum(i=1 to n) sum(j=1 to i) bj

这个双重求和可以换个角度看：每个数字 bj 会被包含在从第 j 位到第 n 位的所有前缀和中，共被累加 (n - j + 1) 次。

核心洞察：位置越靠左，数字被累加的次数越多。第1位的数字被加 n 次，第 n 位的数字只被加1次。

贪心策略：交换论证

假设当前排列不是降序的，存在相邻位置 i 和 i+1 满足 bi < b(i+1)。我们来算一笔账：

• 交换前，这两个位置对总和的贡献为：bi * (n-i+1) + b(i+1) * (n-i)
• 交换后，贡献变为：b(i+1) * (n-i+1) + bi * (n-i)

两者之差：

Delta = (b(i+1) - bi) * [(n-i+1) - (n-i)] = b(i+1) - bi > 0

结论：任何逆序对（小数在大数左边）都可以通过交换使总和变大。因此，降序排列是唯一最优解。

前缀和优化：避免重复计算

直接按贡献度公式 sum bi * (n-i+1) 计算需要两次遍历。更优雅的做法是：

• 先排序，再维护前缀和数组 sa[i] = sa[i-1] + bi
• 总糖果量就是所有前缀和之和：ans = sum(i=1 to n) sa[i]

这样做的优势：

• 代码更简洁，逻辑更直观
• 避免手动计算每个位置的贡献系数
• 为后续扩展（如动态修改、区间查询）留下接口

算法模板

算法到底在干什么？

想象一条传送带，上面放着 n 个包裹，每个包裹上标着重量。规则是：每经过一个包裹，就要把当前传送带上所有包裹的重量加一遍，记为这一站的"运费"。你要做的，就是调整包裹的顺序，让总运费最多。

贪心排序就是：把最重的包裹放在最前面，让它被累加最多次；最轻的放最后面，只累加一次。

万能模板

伪代码：

function maxCandy(n, a):
    sort(a, descending)           // 降序排序
    prefix[0] = 0
    ans = 0
    for i = 1 to n:
        prefix[i] = prefix[i-1] + a[i]
        ans += prefix[i]
    return ans

核心代码（C++）：

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

// 贪心排序 + 前缀和求最大总和
// 适用于：每个元素的贡献与位置权重相关的最优排列问题
long long maxTotal(vector<int>& a) {
    sort(a.begin(), a.end(), greater<int>());  // 降序排列
    long long prefix = 0, ans = 0;
    for (int x : a) {
        prefix += x;      // 维护前缀和
        ans += prefix;    // 累加每个位置的前缀和
    }
    return ans;
}

例题实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1005;                // 常量：最大小朋友数量

int n;                             // n: 小朋友个数
int ans;                           // ans: 最大糖果总数量
int a[N];                          // a[i]: 第 i 个小朋友手上的数字
int sa[N];                         // sa[i]: 前 i 个小朋友数字的前缀和

signed main()
{
    cin >> n;                      // 读入小朋友个数

    for (int i = 1; i <= n; i++)  // 读入 n 个小朋友手上的数字
        cin >> a[i];

    sort(a + 1, a + n + 1, greater<int>());  // 按数字从大到小排序，让大的数字尽量靠左

    for (int i = 1; i <= n; i++)  // 计算最大糖果总量
    {
        sa[i] = sa[i - 1] + a[i];  // 计算前 i 个小朋友数字的前缀和
        ans += sa[i];              // 第 i 个小朋友分到的糖果数 = 前 i 个数字之和，累加到总量
    }

    cout << ans << endl;           // 输出最大糖果总数量

    return 0;
}

对比实现：直接贡献度法

除了前缀和累加，也可以直接按贡献系数计算：

// 方法2：直接计算每个位置的贡献
sort(a + 1, a + n + 1, greater<int>());
long long ans = 0;
for (int i = 1; i <= n; i++) {
    ans += a[i] * (n - i + 1);  // 第i位被累加(n-i+1)次
}

对比表格：

方法	代码量	直观性	扩展性
前缀和累加	稍多	高（模拟实际过程）	好（支持动态修改）
直接贡献度	更少	中（需要理解系数）	差（系数固定）

推荐：竞赛中两种方法均可，前缀和法更符合"模拟题意"的思维习惯。

变体清单

变体类型	题目特征	贪心策略	关键变化
最小化版本	求最小总糖果量	升序排列	贡献度分析方向相反
带权位置	每个位置有额外权重 wi	按 ai/wi 或特定比值排序	可能需要更复杂的排序规则
部分排列	只能选 k 个数字排列	选最大的 k 个，再降序排	增加选择环节
环形排列	小朋友围成一圈	需要断环为链，枚举断点	复杂度升至 O(n^2)
负数元素	数字可能为负	不能简单降序，需分类讨论	正数放左，负数放右

什么时候不能用？

• 元素有负数时：降序排列可能不是最优。例如 [-5, 100, 1]，若按降序排为 [100, 1, -5]，但如果把 -5 放最前面，它只会被加一次（负面影响最小），需要重新分析。
• 位置权重不均匀时：如果每个位置的"被累加次数"不是简单的 (n-i+1)，而是任意给定的权重，可能需要按比值排序或其他策略。
• 约束条件复杂时：如要求某些元素必须相邻、某些位置固定等，贪心可能失效，需要动态规划。

底层逻辑

为什么贪心是对的？

贪心算法的正确性通常需要交换论证或拟阵理论支撑。本题属于前者：

1. 最优子结构：假设最优排列中，前 k 个元素已经确定，那么后 n-k 个元素的排列也必须是这 n-k 个元素的最优排列。
2. 贪心选择性质：每次选择当前最大的未使用元素放在最左侧，不会导致后续无法达到最优。

这两个性质共同保证了：局部最优（每次选最大）能推出全局最优（总和最大）。

与经典问题的对比

问题	相似点	不同点
活动安排问题	都是排序后贪心	按结束时间排序，选相容活动
霍夫曼编码	都是让高频/大权重元素"更省资源"	用堆维护，合并而非排列
调度问题	都是最小化/最大化加权总和	可能涉及多机调度，更复杂

本题的独特之处在于：权重结构是固定的前缀和形式，这使得排序规则特别简单（纯降序），不需要像调度问题那样计算比值或动态调整。

隐含约束的分析

题目中"正整数"这个条件至关重要：

• 若允许负数，大负数放左边会严重拉低总和
• 若允许零，零的位置不影响结果，最优解不唯一
• 正整数保证了严格降序唯一最优，且交换论证中的 Delta > 0 严格成立

决策表

场景特征	推荐方案	核心操作
所有数字为正，求最大前缀和总和	降序排序 + 前缀和累加	sort(…, greater())
所有数字为正，求最小前缀和总和	升序排序 + 前缀和累加	sort(…, less())
数字含负数，求最大总和	分类讨论：正数降序放左，负数升序放右	分段排序
位置有自定义权重 wi	按 ai * wi 贡献排序	自定义比较函数
需要动态修改元素值	树状数组/线段树维护前缀和	数据结构优化
n <= 10^5，需 O(n log n)	上述排序方法均可	标准排序即可
n <= 10^7，需接近 O(n)	计数排序/基数排序	线性时间排序

工程视角

这类"贡献度加权排序"的思想在实际工程中非常常见：

1. 任务调度系统：CPU调度中，短作业优先（SJF）就是让执行时间短的任务"被等待的次数"最少，本质是让"权重"小的任务尽量靠后。反过来，如果每个任务的收益不同，就要按"收益/时间"排序——这正是贪心排序的延伸。

2. 数据库查询优化：在多表连接中，选择最优的连接顺序以最小化中间结果集大小。虽然实际会用动态规划（如PostgreSQL的遗传算法+动态规划），但核心思想与"让大数据量操作尽量靠后"一致。

3. 广告投放策略：假设有 n 个广告位，每个位置的曝光量递减（第1位最多，第n位最少）。要最大化总点击率，应该把点击率最高的广告放在最前面——与本题模型完全一致。

4. 缓存替换策略：LRU（最近最少使用）虽然不是排序问题，但"让高频访问数据更容易被命中"的思想与"让大贡献元素被累加更多次"异曲同工。

小结

这道题教会我们的核心认知是：

当每个元素的贡献与它的位置相关时，最优排列往往可以通过"贡献度分析 + 交换论证"确定，而不需要枚举所有排列。

用公式化语言总结：

最优排列 = sort(a, descending) => max sum(i=1 to n) sum(j=1 to i) aj = sum(i=1 to n) ai * (n - i + 1)

关键认知升级：

• 从"直觉排序"到"证明排序"：不只是觉得"大的放前面好"，而是能用交换论证严格证明
• 从"双重循环"到"前缀和优化"：用前缀和将 O(n^2) 的暴力计算优化到 O(n)
• 从"具体题目"到"通用模型"：识别出"位置权重 * 元素值"这类问题的通用贪心框架

下次遇到"排一排让总和最大/最小"的问题，先问自己：每个位置对总和的贡献是什么？答案往往就藏在排序规则里。