题解：洛谷 P17010 [GESP202606 五级] 排排坐

【题目来源】

洛谷：P17010 [GESP202606 五级] 排排坐 - 洛谷

【题目描述】

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

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

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

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

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

【输入】

输入2 22行，

第一行为一个正整数n nn，表示小朋友的个数；

第二行为n nn个正整数a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_na1​,a2​,⋯,an​，表示小朋友们手上的数字，整数之间以空格分隔。

【输出】

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

【输入样例】

5 7 5 8 9 3

【输出样例】

111

【核心思想】

1. 问题分析：给定n nn个正整数a 1 , a 2 , … , a n a_1, a_2, \ldots, a_na1​,a2​,…,an​，需要安排座位顺序使得糖果总量最大。第i ii个座位的小朋友获得糖果数为前i ii个位置数字之和，总糖果量为所有前缀和之和。这是一个贪心排序问题，核心在于确定最优的排列顺序使得前缀和总和最大。

2. 算法选择：

   • 贪心策略：将较大的数字放在更左侧的位置，使其被累加更多次
   • 前缀和累加：排序后计算前缀和，再累加所有前缀和得到总糖果量

3. 关键步骤：

   • 读入数据：读取n nn和数组a [ 1.. n ] a[1..n]a[1..n]
   • 贪心排序：将a aa按降序排列（从大到小），使得大数字尽量靠左
   • 前缀和计算：s a [ i ] = s a [ i − 1 ] + a [ i ] sa[i] = sa[i-1] + a[i]sa[i]=sa[i−1]+a[i]，s a [ i ] sa[i]sa[i]表示前i ii个位置数字之和
   • 累加总糖果量：a n s ← a n s + s a [ i ] ans \leftarrow ans + sa[i]ans←ans+sa[i]，第i ii个位置的小朋友获得s a [ i ] sa[i]sa[i]个糖果
   • 输出结果：a n s ansans

4. 时间/空间复杂度：

   • 时间复杂度：O ( n log ⁡ n ) O(n \log n)O(nlogn)，排序为O ( n log ⁡ n ) O(n \log n)O(nlogn)，前缀和与累加为O ( n ) O(n)O(n)
   • 空间复杂度：O ( n ) O(n)O(n)，前缀和数组

5. 贪心排序的核心思想：

   • 贡献度分析：位置i ii的数字a i a_iai​对总糖果量的贡献为a i × ( n − i + 1 ) a_i \times (n - i + 1)ai​×(n−i+1)，即该数字会被包含在从位置i ii到位置n nn的所有前缀和中，共被累加( n − i + 1 ) (n - i + 1)(n−i+1)次
   • 交换论证：假设存在相邻位置i ii和i + 1 i+1i+1满足a i < a i + 1 a_i < a_{i+1}ai​<ai+1​，交换后总贡献增加( a i + 1 − a i ) > 0 (a_{i+1} - a_i) > 0(ai+1​−ai​)>0，因此降序排列为最优
   • 前缀和优化：不必单独计算每个位置的贡献系数，直接累加前缀和即可得到总糖果量，因为∑ i = 1 n s a [ i ] = ∑ i = 1 n a i × ( n − i + 1 ) \sum_{i=1}^{n} sa[i] = \sum_{i=1}^{n} a_i \times (n - i + 1)∑i=1n​sa[i]=∑i=1n​ai​×(n−i+1)
   • 正整数保证：题目保证所有数字为正整数，因此大数字放左侧一定更优，无需考虑负数或零的特殊情况
   • 适用于元素贡献与位置相关的最优排列类问题，核心是通过贡献度分析确定贪心策略

【算法标签】

#普及- #前缀和

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1005;// 常量：最大小朋友数量intn;// n: 小朋友个数intans;// ans: 最大糖果总数量inta[N];// a[i]: 第 i 个小朋友手上的数字intsa[N];// sa[i]: 前 i 个小朋友数字的前缀和signedmain(){cin>>n;// 读入小朋友个数for(inti=1;i<=n;i++)// 读入 n 个小朋友手上的数字cin>>a[i];sort(a+1,a+n+1,greater<int>());// 按数字从大到小排序，让大的数字尽量靠左for(inti=1;i<=n;i++)// 计算最大糖果总量{sa[i]=sa[i-1]+a[i];// 计算前 i 个小朋友数字的前缀和ans+=sa[i];// 第 i 个小朋友分到的糖果数 = 前 i 个数字之和，累加到总量}cout<<ans<<endl;// 输出最大糖果总数量return0;}

【运行结果】

5 7 5 8 9 3 111