【题目来源】洛谷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【核心思想】问题分析给定n nn个正整数a 1 , a 2 , … , a n a_1, a_2, \ldots, a_na1​,a2​,…,an​需要安排座位顺序使得糖果总量最大。第i ii个座位的小朋友获得糖果数为前i ii个位置数字之和总糖果量为所有前缀和之和。这是一个贪心排序问题核心在于确定最优的排列顺序使得前缀和总和最大。算法选择贪心策略将较大的数字放在更左侧的位置使其被累加更多次前缀和累加排序后计算前缀和再累加所有前缀和得到总糖果量关键步骤读入数据读取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←anssa[i]第i ii个位置的小朋友获得s a [ i ] sa[i]sa[i]个糖果输出结果a n s ansans时间/空间复杂度时间复杂度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)前缀和数组贪心排序的核心思想贡献度分析位置i ii的数字a i a_iai​对总糖果量的贡献为a i × ( n − i 1 ) a_i \times (n - i 1)ai​×(n−i1)即该数字会被包含在从位置i ii到位置n nn的所有前缀和中共被累加( n − i 1 ) (n - i 1)(n−i1)次交换论证假设存在相邻位置i ii和i 1 i1i1满足a i a i 1 a_i a_{i1}ai​ai1​交换后总贡献增加( a i 1 − a i ) 0 (a_{i1} - a_i) 0(ai1​−ai​)0因此降序排列为最优前缀和优化不必单独计算每个位置的贡献系数直接累加前缀和即可得到总糖果量因为∑ i 1 n s a [ i ] ∑ i 1 n a i × ( n − i 1 ) \sum_{i1}^{n} sa[i] \sum_{i1}^{n} a_i \times (n - i 1)∑i1n​sa[i]∑i1n​ai​×(n−i1)正整数保证题目保证所有数字为正整数因此大数字放左侧一定更优无需考虑负数或零的特殊情况适用于元素贡献与位置相关的最优排列类问题核心是通过贡献度分析确定贪心策略【算法标签】#普及- #前缀和【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN1005;// 常量最大小朋友数量intn;// n: 小朋友个数intans;// ans: 最大糖果总数量inta[N];// a[i]: 第 i 个小朋友手上的数字intsa[N];// sa[i]: 前 i 个小朋友数字的前缀和signedmain(){cinn;// 读入小朋友个数for(inti1;in;i)// 读入 n 个小朋友手上的数字cina[i];sort(a1,an1,greaterint());// 按数字从大到小排序让大的数字尽量靠左for(inti1;in;i)// 计算最大糖果总量{sa[i]sa[i-1]a[i];// 计算前 i 个小朋友数字的前缀和anssa[i];// 第 i 个小朋友分到的糖果数 前 i 个数字之和累加到总量}coutansendl;// 输出最大糖果总数量return0;}【运行结果】5 7 5 8 9 3 111